Degree conditions for the partition of a graph into cycles, edges and isolated vertices
Degree conditions for the partition of a graph into cycles, edges and isolated vertices
复制标题
DOI：
10.1016/j.disc.2007.12.056
复制
发表时间：
2009-06
期刊：
影响因子：
--
通讯作者：
S. Fujita
中科院分区：
文献类型：
--
作者：
S. Fujita
设k，n为2≤k≤n的整数，设G为n阶图。我们证明如果max{dG(x),dG(y)}≥(n−k+1)/2，对于任意x，y∈V(G)，且x≠y， xy∈E(G)，则G有k个顶点不相交的子图H1，…，hk使得V(H1)∪⋯∪V(Hk)=V(G)且hi1是一个循环或K1或k2，对于每个1≤i≤k，除非k=2且G=C5，或k=3且G=K1∪C5。
Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{dG(x),dG(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H1,…,Hksuch that V(H1)∪⋯∪V(Hk)=V(G) and Hiis a cycle or K1or K2for each 1≤i≤k, unless k=2 and G=C5, or k=3 and G=K1∪C5.