标题:Vertex-disjoint copies of K-1,K-t in K-1,K-r-free graphs
作者:Jiang, Suyun; Chiba, Shuya; Fujita, Shinya; Yan, Jin
作者机构:[Jiang, Suyun; Yan, Jin] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China.; [Chiba, Shuya] Kumamoto Univ, Fac Adv Sci & Technol, App 更多
通讯作者:Yan, J
通讯作者地址:[Yan, J]Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China.
来源:DISCRETE MATHEMATICS
出版年:2017
卷:340
期:4
页码:649-654
DOI:10.1016/j.disc.2016.11.034
关键词:K-1,K-r-free graph; Vertex-disjoint stars; Minimum degree
摘要:A graph G is said to be K-1,K-r-free if G does not contain an induced subgraph isomorphic to K-1,K-r. Let k, r, t be integers with k >= 2 and t >= 3. In this paper, we prove that if G is a K-1,K-r-free graph of order at least (k - 1)(t(r - 1)+1) + 1 with delta(G) >= t and r >= 2t 1, then G contains k vertex-disjoint copies of K-1,K- t. This result shows that the conjecture in Fujita (2008) is true for r >= 2t - 1 and t >= 3. Furthermore, we obtain a weaker version of Fujita's conjecture, that is, if G is a K-1,K-r-free graph of order at least (k - 1)(t(r - 1) + 1 (t - 1)(t - 2)) + 1 with delta(G) >= t and r >= 6, then G contains k vertex-disjoint copies of K-1,K-t. (C) 2016 Elsevier B.V. All rights reserved.
收录类别:SCOPUS;SCIE
Scopus被引频次:1
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-85007575509&doi=10.1016%2fj.disc.2016.11.034&partnerID=40&md5=f2f30a603e775054fc93d07e4cebf9a2
TOP