Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths

DOI10.1112/PLMS/PDT051MaRDI QIDQ4979770zbMATH OpenOpenAlexFDO

Authors Darryn Bryant, Daniel Horsley, William Pettersson

Publication date 19 June 2014

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1204.3709

zbMATH Keywords

decompositioncyclescomplete graphSteiner triple systemHamilton decompositionAlspach's problemperfect matchig

Mathematics Subject Classification ID

Other designs, configurations (05B30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We show that the complete graph on $n$ vertices can be decomposed into $t$ cycles of specified lengths $m_1,ldots,m_t$ if and only if $n$ is odd, $3leq{m}_{i}leqn$ for $i=1,ldots,t$, and $$. 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,ldots,m_t$ if and only if $n$ is even, $3leq{m}_{i}leqn$ for $i=1,ldots,t$, and $$.

Recommendations

• An asymptotic solution to the cycle decomposition problem for complete graphs
• Cycle decompositions of complete graphs
• Decomposing the complete graph into cycles of many lengths
• scientific article; zbMATH DE number 786153
• Cycle decompositions of complete multigraphs

Cited in

(56)

• Decompositions of complete equipartite graphs into cycles of lengths 3 and 6
• Decomposing \(K_{u + w} - K_u\) into cycles of prescribed lengths
• Decompositions of complete multigraphs into cycles of varying lengths
• GENERALISATIONS OF THE DOYEN–WILSON THEOREM
• Decompositions of complete graphs into blown-up cycles \(C_m\)[2]
• The generalised Oberwolfach problem
• On the spouse-loving variant of the Oberwolfach problem
• Eulerian cycle decomposition conjecture for the line graph of complete graphs
• Alspach's problem: The case of Hamilton cycles and 5-cycles
• Equitable block-colorings of \(C_4\)-decompositions of \(K_v-F\)
• Cycle decompositions of the complete graph.
• scientific article; zbMATH DE number 536589 (Why is no real title available?)
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• A \(C_5\)-decomposition of the \(\lambda\)-fold line graph of the complete graph
• Cycle decompositions of complete digraphs
• On equitably 2-colourable odd cycle decompositions
• On Alspach's conjecture
• Cycle decompositions of complete multigraphs
• Some results on decompositions of low degree circulant graphs
• Decompositions of complete graphs into circulants
• scientific article; zbMATH DE number 4123776 (Why is no real title available?)
• Cyclically decomposing the complete graph into cycles
• An asymptotic solution to the cycle decomposition problem for complete graphs
• 2p-cycle decompositions of some regular graphs and digraphs
• On decomposing K_n -I into cycles of a fixed odd length
• \((4, 5)\)-cycle systems of complete multipartite graphs
• A blow-up lemma for approximate decompositions
• scientific article; zbMATH DE number 4066956 (Why is no real title available?)
• Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking
• A survey on constructive methods for the Oberwolfach problem and its variants
• Almost resolvable decompositions of \(2K_ n\) into cycles of odd length
• Decomposing the complete graph into cycles of many lengths
• Decompositions of complete tripartite graphs into cycles of lengths 3 and 6
• Decompositions of some classes of regular graphs and digraphs into cycles of length \(4p\)
• Decompositions of some classes of dense graphs into cycles of lengths 4 and 8
• Decomposition of the tensor product of complete graphs into cycles of lengths 3 and 6
• Face 2-Colorable Embeddings with Faces of Specified Lengths
• \(C_{p}\)-decompositions of some regular graphs
• Cycle packings of the complete multigraph
• Resolution of the Oberwolfach problem
• Decompositions of some regular graphs into unicyclic graphs of order five
• Cycle decompositions of complete graphs
• Resolution of the Oberwolfach problem
• scientific article; zbMATH DE number 822734 (Why is no real title available?)
• Cycle decompositions. IV: Complete directed graphs and fixed length directed cycles
• Decomposition of complete bipartite graphs into cycles of distinct even lengths
• On decomposing the complete graph into the union of two disjoint cycles
• Decompositions of complete graphs into long cycles
• A novel approach for cyclic decompositions of balanced complete bipartite graphs into infinite graph classes
• Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach
• scientific article; zbMATH DE number 786153 (Why is no real title available?)
• Doyen-Wilson results for odd length cycle systems
• Decompositions of complete graphs into triangles and Hamilton cycles
• Cyclically decomposing the complete graph into 2-regular graphs
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes
• Decompositions of line graphs of complete graphs into paths and cycles

This page was built for publication: Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4979770)