Decompositions of complete graphs into paths and cycles. (English) Zbl 1249.05313

Summary: Let \(P_{k+1}\) denote the path of length \(k\) and let \(C_k\) denote the cycle of length \(k\). As usual, \(K_n\) denotes the complete graph on \(n\) vertices. In this paper we investigate decompositions of \(K_n\) into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing \(K_n\) into \(p\) copies of \(P_5\) and \(q\) copies of \(C_4\) for all possible values of \(p\geq 0\) and \(q\geq 0\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles