Premium
On the Hamilton–Waterloo problem with odd cycle lengths
Author(s) -
Burgess A. C.,
Danziger P.,
Traetta T.
Publication year - 2018
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.21586
Subject(s) - mathematics , combinatorics , lexicographical order , graph , graph factorization , complete graph , factorization , hamiltonian path , discrete mathematics , line graph , graph power , algorithm
Let K v ∗ denote the complete graph K v if v is odd andK v − I , the complete graph with the edges of a 1‐factor removed, if v is even. Given nonnegative integers v , M , N , α , β , the Hamilton–Waterloo problem asks for a 2‐factorization of K v ∗ into α C M ‐factors and β C N ‐factors, with a C ℓ ‐factor of K v ∗ being a spanning 2‐regular subgraph whose components are ℓ‐cycles. Clearly, M , N ≥ 3 , M ∣ v , N ∣ v and α + β = ⌊ v − 1 2 ⌋ are necessary conditions. In this paper, we extend a previous result by the same authors and show that for any odd v ≠ M N gcd ( M , N )the above necessary conditions are sufficient, except possibly when α = 1 , or when β ∈ { 1 , 3 } . Note that in the case where v is odd, M and N must be odd. If M and N are odd but v is even, we also show sufficiency but with further possible exceptions. In addition, we provide results on 2‐factorizations of the complete equipartite graph and the lexicographic product of a cycle with the empty graph.