Partition of a graph into cycles and degenerated cycles Original Research Article

Let G be a graph of order n and k any positive integer with k⩽n. It has been shown by Brandt et al. that if |G|=n⩾4k and if the degree sum of any pair of nonadjacent vertices is at least n, then G can be partitioned into k cycles. We prove that if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G can be partitioned into k subgraphs Hi, 1⩽i⩽k, where Hi is a cycle or K1 or K2, except G=C5 and k=2.