Packing cycles in complete graphs

Darryn Bryant, Daniel Horsley

Research output: Contribution to journalArticleResearchpeer-review

19 Citations (Scopus)

Abstract

We introduce a new technique for packing pairwise edge-disjoint cycles of specified lengths in complete graphs and use it to prove several results. Firstly, we prove the existence of dense packings of the complete graph with pairwise edge-disjoint cycles of arbitrary specified lengths. We then use this result to prove the existence of decompositions of the complete graph of odd order into pairwise edge-disjoint cycles for a large family of lists of specified cycle lengths. Finally, we construct new maximum packings of the complete graph with pairwise edge-disjoint cycles of uniform length.
Original languageEnglish
Pages (from-to)1014 - 1037
Number of pages24
JournalJournal of Combinatorial Theory, Series B
Volume98
Issue number5
DOIs
Publication statusPublished - 2008
Externally publishedYes

Cite this