Vertex-disjoint copies of K1,t in K1,r-free graphs

被引：1

作者：

Jiang, Suyun ^{[1
]}

Chiba, Shuya ^{[2
]}

Fujita, Shinya ^{[3
]}

Yan, Jin ^{[1
]}

机构：

[1] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China

[2] Kumamoto Univ, Fac Adv Sci & Technol, Appl Math, 2-39-1 Kurokami, Kumamoto 8608555, Japan

[3] Yokohama City Univ, Int Coll Arts & Sci, Kanazawa Ku, 22-2 Seto, Yokohama, Kanagawa 2360027, Japan

来源：

DISCRETE MATHEMATICS | 2017年 / 340卷 / 04期

关键词：

K-1; K-r-free graph; Vertex-disjoint stars; Minimum degree; K-1;

D O I：

10.1016/j.disc.2016.11.034

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：649 / 654

页数：6