Doyen-Wilson results for odd length cycle systems

2014/11/14 by Daniel Horsley, Horsley, Daniel, Rosalind A. Hoyte +1 · 1 citation
Mathematics · #05B30 (Secondary) #05C38 #05C51 (Primary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05B30 #msc:05C38 #msc:05C51

paper · pdf · doi:10.48550/arxiv.1411.3785

28 pages, 0 figures

arxiv created 2015/06/12 · arxiv updated 2015/06/15

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 which 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.

Cited by

• Decomposing K_u+w-K_u into cycles of various lengths

Related

• Decomposing various graphs into short even-length cycles
• Completing the spectrum of almost resolvable cycle systems with odd cycle length
• Minimum degree conditions for the existence of a sequence of cycles whose lengths differ by one or two
• The Hamilton-Waterloo Problem with even cycle lengths
• Almost 2-perfect 8-cycle systems