Premium
The Hamilton—Waterloo problem: The case of triangle‐factors and one Hamilton cycle
Author(s) -
Dinitz J.H.,
Ling Alan C.H.
Publication year - 2009
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.20196
Subject(s) - mathematics , combinatorics , hamiltonian path , factor (programming language) , factorization , algorithm , computer science , graph , programming language
The Hamilton—Waterloo problem is to determine the existence of a 2‐factorization of K 2 n +1 in which r of the 2‐factors are isomorphic to a given 2‐factor R and s of the 2‐factors are isomorphic to a given 2‐factor S , with r + s = n . In this article we consider the case when R is a triangle‐factor, S is a Hamilton cycle and s = 1. We solve the problem completely except for 14 possible exceptions. This solves a major open case from the 2004 article of Horak et al. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 160–176, 2009