Cycle packings of the complete multigraph

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,\dots ,m_{\tau }$. In this paper we characterise exactly when there exists a packing of the complete multigraph with cycles of specified lengths $m_1,m_2,\dots ,m_{\tau }$. 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.

9 pages, 0 figures

References in corpus (1)

• Decompositions of complete graphs into cycles of arbitrary lengths