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) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.