Cycle packings of the complete multigraph

MaRDI QIDQ4622608zbMATH OpenFDO

Authors Rosalind A. Cameron

Publication date 13 February 2019

Full work available at URL https://arxiv.org/abs/1701.05287, http://ajc.maths.uq.edu.au/pdf/72/ajc_v72_p128.pdf

zbMATH Keywords

complete multigraphcycle decompositionedge decomposition

Mathematics Subject Classification ID

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

Abstract: Bryant, Horsley, Maenhaut and Smith recently gave necessary and sufficient conditions for when the complete multigraph can be decomposed into cycles of specified lengths $m_1,m_2,ldots,m_{a}u$. In this paper we characterise exactly when there exists a packing of the complete multigraph with cycles of specified lengths $m_1,m_2,ldots,m_{a}u$. While cycle decompositions can give rise to packings by removing cycles from the decomposition, in general it is not known when there exists a packing of the complete multigraph with cycles of various specified lengths.

Recommendations

• Decompositions of complete multigraphs into cycles of varying lengths
• Cycle decompositions of complete multigraphs
• Cycle decompositions of complete multigraphs
• Packing cycles in complete graphs
• Decompositions of complete multipartite graphs into cycles of even length

Cites work

• Cycle decompositions of K_n and K_n-I
• Cycle decompositions of complete multigraphs
• Cycle decompositions of complete multigraphs
• Cycle decompositions. III: Complete graphs and fixed length cycles.
• Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths
• Decompositions of complete graphs into long cycles
• Decompositions of complete multigraphs into cycles of varying lengths
• Maximum packings of the complete graph with uniform length cycles
• Maximum packings with odd cycles
• On the Alspach conjecture
• Packing cycles in complete graphs

Cited in

(7)

• Packing cycles in graphs. II
• Packing 5-cycles into balanced complete \(m\)-partite graphs for odd \(m\)
• Universal cycle packings and coverings for \(k\)-subsets of an \(n\)-set
• On maximum cycle packings in polyhedral graphs
• Cycle decompositions of complete multigraphs
• Decompositions of complete multigraphs into cycles of varying lengths
• Packing cycles in complete graphs

This page was built for publication: Cycle packings of the complete multigraph

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