Decomposition of complete graphs into paths and stars

Let Pk+1Pk+1 denote a path of length kk and let Sk+1Sk+1 denote a star with kk edges. As usual KnKn denotes the complete graph on nn vertices. In this paper we investigate the decomposition of KnKn into paths and stars, and prove the following results.Theorem A. Let pp and qq be nonnegative integers and let nn be a positive integer. There exists a decomposition of KnKn into pp copies of P4P4 and qq copies of S4S4 if and only if n≥6n≥6 and 3(p+q)=n2.Theorem B. Let pp and qq be nonnegative integers, let nn and kk be positive integers such that n≥4kn≥4k and k(p+q)=n2, and let one of the following conditions hold: (1)k is even and p≥k2,(2)k is odd and p≥kk is odd and p≥k. Then there exists a decomposition of KnKn into pp copies of Pk+1Pk+1 and qq copies of Sk+1Sk+1.