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

Melissa S. Keranen, Adrián Pastine


The Hamilton-Waterloo problem asks for a decomposition of the complete graph of order v into r copies of a 2-factor F1 and s copies of a 2-factor F2 such that r + s = ⌊(v − 1) / 2⌋. If F1 consists of m-cycles and F2 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 (2kx, 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}.


2-factorizations, Hamilton-Waterloo problem, Oberwolfach problem, cycle decomposition, resolvable decompositions

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1610.03d

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications