Doyen-Wilson results for odd length cycle systems

Daniel Horsley, Rosalind A. Hoyte

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

For each odd m≥3, we completely solve the problem of when an m-cycle system of order u can be embedded in an m-cycle system of order v, barring a finite number of possible exceptions. In cases where u is large compared to m, where m is a prime power, or where m≤15, the problem is completely resolved. In other cases, the only possible exceptions occur when v-u is small compared to m. This result is proved as a consequence of a more general result that gives necessary and sufficient conditions for the existence of an m-cycle decomposition of a complete graph of order v with a hole of size u in the case where u≥m-2 and v-u≥m+1 both hold.

Original languageEnglish
Pages (from-to)308-335
Number of pages28
JournalJournal of Combinatorial Designs
Volume24
Issue number7
DOIs
Publication statusPublished - 1 Jul 2016

Keywords

  • cycle system
  • Doyen-Wilson theorem
  • graph decomposition
  • subsystem

Cite this