Decompositions of complete graphs into cycles of arbitrary lengths

Abstract

We show that the complete graph on $n$ vertices can be decomposed into $t$ cycles of specified lengths $m_1,\dots ,m_t$ if and only if $n$ is odd, $3\le m_i\le n$ for $i=1,\dots ,t$, and $m_1+\cdots +m_t=\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. We also show that the complete graph on $n$ vertices can be decomposed into a perfect matching and $t$ cycles of specified lengths $m_1,\dots ,m_t$ if and only if $n$ is even, $3\le m_i\le n$ for $i=1,\dots ,t$, and $m_1+\dots +m_t=\left(\genfrac{}{}{0ex}{}{n}{2}\right)-\frac{n}{2}$.

182 pages, 0 figures, A condensed version of this paper was published as "Cycle decompositions V: Complete graphs into cycles of arbitrary lengths" (see reference [24]). Here, we include supplementary data and some proofs which were omitted from that paper

References in corpus (1)

• Decompositions of complete graphs into cycles of arbitrary lengths

Cited by in corpus (11)

• Hamilton cycles in graphs and hypergraphs: an extremal perspective
• Decompositions of complete graphs into cycles of arbitrary lengths
• Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach
• Universal quantum processors in spin systems via robust local pulse sequences
• A blow-up lemma for approximate decompositions
• Partitioning de Bruijn Graphs into Fixed-Length Cycles for Robot Identification and Tracking
• Partitioning The Edge Set of a Hypergraph Into Almost Regular Cycles
• Cycle packings of the complete multigraph
• Enclosings of Decompositions of Complete Multigraphs in $2$-Edge-Connected $r$-Factorizations
• Decompositions of complete uniform multi-hypergraphs into Berge paths and cycles of arbitrary lengths
• Decomposing $K_{u+w}-K_u$ into cycles of various lengths