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

DOI10.1112/PLMS/PDT051zbMATH Open1296.05044arXiv1204.3709OpenAlexW2102407078MaRDI QIDQ4979770FDOQ4979770

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)

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

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

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

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)

Cited In (56)

• GENERALISATIONS OF THE DOYEN–WILSON THEOREM
• Decomposing \(K_{u + w} - K_u\) into cycles of prescribed lengths
• Decompositions of complete multigraphs into cycles of varying lengths
• Decompositions of complete graphs into blown-up cycles \(C_m\)[2]
• On the spouse-loving variant of the Oberwolfach problem
• The generalised Oberwolfach problem
• Eulerian cycle decomposition conjecture for the line graph of complete graphs
• Cycle decompositions of the complete graph.
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• Title not available (Why is that?)
• Alspach's problem: The case of Hamilton cycles and 5-cycles
• Equitable block-colorings of \(C_4\)-decompositions of \(K_v-F\)
• 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
• Title not available (Why is that?)
• Cyclically decomposing the complete graph into cycles
• Decompositions of complete graphs into circulants
• 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
• A blow-up lemma for approximate decompositions
• \((4, 5)\)-cycle systems of complete multipartite graphs
• Title not available (Why is that?)
• A survey on constructive methods for the Oberwolfach problem and its variants
• Partitioning de Bruijn graphs into fixed-length cycles for robot identification and tracking
• Almost resolvable decompositions of \(2K_ n\) into cycles of odd length
• 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\)
• Decomposing the complete graph into cycles of many lengths
• 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
• Cycle decompositions of complete graphs
• Decompositions of some regular graphs into unicyclic graphs of order five
• Title not available (Why is that?)
• Resolution of the Oberwolfach problem
• 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
• Cycle decompositions. IV: Complete directed graphs and fixed length directed 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
• Title not available (Why is that?)
• 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
• Decompositions of complete equipartite graphs into cycles of lengths 3 and 6

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)