On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity

Abstract

The Hamilton-Waterloo problem asks for a decomposition of the complete graph of order v into r copies of a 2-factor F₁ and s copies of a 2-factor F₂ such that r + s = ⌊(v − 1) / 2⌋. If F₁ consists of m-cycles and F₂ consists of n cycles, we say that a solution to (m, n)-HWP(v; r, s) exists. The goal is to find a decomposition for every possible pair (r, s). In this paper, we show that for odd x and y, there is a solution to (2^kx, y)-HWP(vm; r, s) if gcd (x, y) ≥ 3, m ≥ 3, and both x and y divide v, except possibly when 1 ∈ {r, s}.