Premium
On the Hamilton–Waterloo Problem with Odd Orders
Author(s) -
Burgess A. C.,
Danziger P.,
Traetta T.
Publication year - 2017
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21552
Subject(s) - lexicographical order , mathematics , combinatorics , factorization , graph , generality , order (exchange) , product (mathematics) , discrete mathematics , algorithm , psychology , geometry , finance , economics , psychotherapist
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.