Degree conditions for the partition of a graph into cycles, edges and isolated vertices |
| |
Authors: | Shinya Fujita |
| |
Institution: | Department of Mathematics, Gunma National College of Technology, 580 Toriba, Maebashi, Gunma 371-8530, Japan |
| |
Abstract: | 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,…,Hk such that V(H1)∪?∪V(Hk)=V(G) and Hi is a cycle or K1 or K2 for each 1≤i≤k, unless k=2 and G=C5, or k=3 and G=K1∪C5. |
| |
Keywords: | Vertex-disjoint cycles Degree conditions Partition of a graph |
本文献已被 ScienceDirect 等数据库收录! |
|