Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4648579 | Discrete Mathematics | 2009 | 7 Pages |
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
Shinya Fujita,