## 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$$.

### MSC:

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

### Keywords:

graph decomposition; path; cycle; complete graph