A Note on Partition of a Graph into Cycles and Degenerated Cycles
Xu Xin · 2003
Let G be a graph of order n and k be any positive integer with 2≤k≤n. In this paper, we prove that if the maximum degree of any pair of nonadjacent vertices is at least (n-k+3)2 (2≤k≤n), then G can be partitioned into k subgraphs H i, 1≤i≤k, where H i is a cycle or K 1 or K 2.