无爪图中点不相交的特殊四阶子图

Vertex-disjoint Copies of Specified Subgraphs of Order Four in Claw-free Graphs

如果图中不存在同构于K_(1.3)的诱导子图,则称这样的图为无爪图.令K_4^-表示从K_4中去掉一条边后得到的图.Faudree等人研究了无爪图中点不交三角形的个数与其最小度之间的关系,受此启发,我们研究了无爪图中点不交的K_4^-个数与其最小度以及阶数之间的关系.设G是阶数为n且最小度为δ≥5的无爪图,我们证明了G中包含至少((δ-4)/(7δ-8))n个点不交的K_4^-.作为推论,每—个阶数n≥28且δ>(n/7)等的无爪图至少包含(n-7)-2个点不交的K_4^-.

A graph is called claw-free graph if it does not contain an induced subgraph isomorphic to K1,3. Let K4- denote the graph which obtained from K4 by removing exactly one edge. Cycles in claw-free graphs have been well studied by some researchers, in particular, the relation between the number of vertex-disjoint triangles and the minimum degree in claw-free graphs were presented by Faudree et al. Motivated by this, we consider the maximum number of vertex-disjoint K4- in claw-free graphs in terms of the graph order and minimum degree, which can been viewed as a generalization from cycles to specified subgraphs. Let G be a claw-free graph with order n and minimum degree 6 〉 5, by constructing method and the skill of packing subgraphs, we prove that G admits at least （δ-4/7δ-i）n vertexdisjoint copies of K4-. As a corollary, we show that every claw-free graph with order n 〉 28 and δ 〉 n/7 contains at least n/7 - 2 vertex-disjoint copies of K4.