Premium
On the Hamilton‐Waterloo Problem for Bipartite 2‐Factors
Author(s) -
Bryant Darryn,
Danziger Peter,
Dean Matthew
Publication year - 2012
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.21312
Subject(s) - combinatorics , mathematics , bipartite graph , complete bipartite graph , hamiltonian path , graph , discrete mathematics
Given two 2‐regular graphs F 1 and F 2 , both of order n , the Hamilton‐Waterloo Problem for F 1 and F 2 asks for a factorization of the complete graph K n into α 1 copies of F 1 , α 2 copies of F 2 , and a 1‐factor if n is even, for all nonnegative integers α 1 and α 2 satisfyingα 1 + α 2 = ⌊ n − 1 2 ⌋ . We settle the Hamilton‐Waterloo Problem for all bipartite 2‐regular graphs F 1 and F 2 where F 1 can be obtained from F 2 by replacing each cycle with a bipartite 2‐regular graph of the same order.