On the Hamilton-Waterloo Problem with odd orders

الأصل · EN

Given non-negative integers v, m, n, α, β, the Hamilton-Waterloo problem asks for a factorization of the complete graph Kᵥ into α Cₘ-factors and β Cₙ-factors. 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 m and n the necessary conditions are sufficient when v is a multiple of mn and v>mn, except possibly when β=1 or 3, with five additional possible exceptions in (m,n,β). For the case where v=mn we show sufficiency when β> (n+5)/2 except possibly when (m,α) = (3,2), (3,4), with seven further possible exceptions in (m,n,α,β). We also show that when n≥ m≥ 3 are odd integers, the lexicographic product of Cₘ with the empty graph of order n has a factorization into α Cₘ-factors and β Cₙ-factors for every 0≤ α≤ n, β= n-α, except possibly when α= 2,4, β= 1, 3, with three additional possible exceptions in (m,n,α).