Weak saturation number for multiple copies of the complete graph with a star removed

详细信息    查看全文

• 作者：Liqun Pu ; ^{liqunpu@sina.com" class="auth_mail" title="E-mail the corresponding author} ; Yajuan Cui ^{cuiyajuan08@126.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Saturated graphs ; Weak saturation ; Multiple copies
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：11 May 2016
• 年：2016
• 卷：204
• 期：Complete
• 页码：216-220
• 全文大小：604 K

文摘

Let K_t$K_t$ denote the complete graph with t$t$ vertices, and let K_1,m$K_{1,m}$ (a star with m$m$ edges) denote the complete bipartite graph with partite sets of sizes 1 and m$m$. A graph G$G$ of order n$n$ is weakly  F$F$-saturated   if G$G$ contains no copy of F$F$, and there is an ordering of the edges in E(K_n∖G)$E(K_n\setminus G)$ so that if they are added one at a time, then each edge added creates a new copy of F$F$. In this paper, the weak saturation number of multiple copies of K_t−K_1,m$K_t-K_{1,m}$ is determined for positive integers t$t$ and $m(1\le m<t-1)$. This completely answers the question 3 in paper Faudree et al. (2013), partially answers the question 4 in paper Faudree et al. (2013) and the question 1 in Faudree and Gould (2014).