The Hamilton–Waterloo Problem HWP(v;m,n;α,β) asks for a 2-factorization of the complete graph K_v or K_v −I, the complete graph with the edges of a 1-factor removed, into α C_m-factors and β C_n-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 (mod 4). 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.
The Hamilton–Waterloo Problem with even cycle lengths
Traetta T.
2019-01-01
Abstract
The Hamilton–Waterloo Problem HWP(v;m,n;α,β) asks for a 2-factorization of the complete graph K_v or K_v −I, the complete graph with the edges of a 1-factor removed, into α C_m-factors and β C_n-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 (mod 4). 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
