Decomposition of Complete Graphs into Cycles and Stars

Let C _k denote a cycle of length k and let S _k denote a star with k edges. As usual K _n denotes the complete graph on n vertices. In this paper we investigate decomposition of K _n into C _l ’s and S _k ’s, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of K _n into p copies of C ₄ and q copies of S ₄ if and only if ${4(p + q)={n choose 2}, qne 1}$ if n is odd, and ${qgeq max{3, lceil{frac{n}{4}rceil}}}$ if n is even.