On the Hamilton–Waterloo Problem with Odd Orders

Given nonnegative integers v , m , n , α , β , the Hamilton–Waterloo problem asks for a factorization of the complete graph K v into α C m ‐factors and β C n ‐factors. Without loss of generality, we may assume that n ≥ m . Clearly, v odd, n , m ≥ 3 , m ∣ v , n ∣ v and α + β = ( v − 1 ) / 2 are necessary conditions. To date results have only been found for specific values of m and n . In this paper, we show that for any integers n ≥ m , these necessary conditions are sufficient when v is a multiple of m n and v > m n , except possibly when β = 1 or 3. For the case where v = m n we show sufficiency when β > ( n + 5 ) / 2 with some possible exceptions. We also show that when n ≥ m ≥ 3 are odd integers, the lexicographic product of C m with the empty graph of order n has a factorization into α C m ‐factors and β C n ‐factors for every 0 ≤ α ≤ n , β = n − α , with some possible exceptions.