Article ID Journal Published Year Pages File Type
4648579 Discrete Mathematics 2009 7 Pages PDF
Abstract

Let k,nk,n be integers with 2≤k≤n2≤k≤n, and let GG be a graph of order nn. We prove that if max{dG(x),dG(y)}≥(n−k+1)/2max{dG(x),dG(y)}≥(n−k+1)/2 for any x,y∈V(G)x,y∈V(G) with x≠yx≠y and xy∉E(G)xy∉E(G), then GG has kk vertex-disjoint subgraphs H1,…,HkH1,…,Hk such that V(H1)∪⋯∪V(Hk)=V(G)V(H1)∪⋯∪V(Hk)=V(G) and HiHi is a cycle or K1K1 or K2K2 for each 1≤i≤k1≤i≤k, unless k=2k=2 and G=C5G=C5, or k=3k=3 and G=K1∪C5G=K1∪C5.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,