Cycle packings of the complete multigraph

2017/01/19 by Rosalind A. Cameron, Cameron, Rosalind A.
Computer Science · Engineering · Mathematics · #05C38 #05C51 #05C70 #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1701.05287

openalex publication_date 2017/01/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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₁,m₂,…,m_τ. In this paper we characterise exactly when there exists a packing of the complete multigraph with cycles of specified lengths m₁,m₂,…,m_τ. 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.

Related

• Decompositions of complete multigraphs into cycles of varying lengths
• Decomposing K_u+w-K_u into cycles of various lengths
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes
• Decomposing various graphs into short even-length cycles
• m-Cycle Packings of (λ+μ)K_v+u-λK_v: m even