2018/10/04 by Burgess, A. C., Danziger, P., Traetta, T.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1810.02009
The Hamilton-Waterloo Problem HWP(v;m,n;α,β) asks for a 2-factorization of the complete graph Kv or Kv-I, the complete graph with the edges of a 1-factor removed, into α Cm-factors and β Cn-factors, where 3 ≤ m < n. In the case that m and n are both even, the problem has been solved except possibly when 1 ∈ \α,β\ or when α and β are both odd, in which case necessarily v ≡ 2 \pmod4. In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to HWP(v;2m,2n;α,β) for odd α and β whenever the obvious necessary conditions hold, except possibly if β=1; β=3 and gcd(m,n)=1; α=1; or v=2mn/gcd(m,n). This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above.