On the Hamilton-Waterloo problem
type: Item
instance of: scholarly article
title: On the Hamilton-Waterloo problem
zbMATH Open document ID: 0995.05116
author: Darryn Bryant
author: S. I. El-Zanati
author: P. Adams
author: Elizabeth J. Billington
published in: Graphs and Combinatorics
publication date: 2002-05-14T00:00:00Z
review text: The Hamilton-Waterloo problem is a generalization of the well-known Oberwolfach problem, which asks whether it is possible to seat \(n\) people at \(t\) round tables at which there are \(a_1,a_2,..., a_t\) (with \(a_1+ a_2+\cdots+ a_t= n\) and \(a_i\geq 3\), \(1\leq j\leq t\)) on \((n-1)/2\) days such that each person sits next to every other person exactly once. The Oberwolfach problem was first formulated by Ringel in 1967 and relates to possible seating arrangements at a conference in Oberwolfach, Germany. The problem was first mentioned by Guy. The Oberwolfach problem asks for a 2-factorization of the complete graph \(K_n\) in which each 2-factor consists of cycles of lengths \(a_1,a_2,\dots, a_t\). It is clearly necessary that \(n\) must be odd, but it is common to extend the Oberwolfach problem to the case when \(n\) is even by considering 2-factorization of the complete graph of even order with a 1-factor \(F\) removed, denoted \(K_n-F\). In both the cases (\(n\) is odd and \(n\) is even), if such a 2-factorization exists, then \(\text{OP}(a_1,a_2,\dots, a_t)\) is said to have a solution. If the 2-factors consist of \(t\) cycles all of the same length \(m\), that is, \(\text{OP}(m,m,\dots, m)\), then the notation \(\text{OP}(m;t)\) is used. Thus the Hamilton-Waterloo problem asks for a 2-factorization of \(K_v\) in which \(r\) of the 2-factors consist of cycles of lengths \(a_1,a_2,\dots, a_t\) and the remaining \(s\) 2-factors consist of cycles of lengths \(b_1,b_2,\dots, b_u\) (where necessarily \(\sum^t_{i=1} a_i \sum^u_{j=1} b_j= v\)). In this paper the authors consider this Hamilton-Waterloo problem in the case \(a_i= m\), \(1\leq i\leq t\) and \(b_j= n\), \(1\leq j\leq u\). They obtain some general conditions, and apply these to obtain results for \((m,n)\in \{(4,6),(4,8),(4,16), (8,16),(3,5), (3,15),(5,15)\}\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05B30
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 1740502
zbMATH Keywords: decomposition
zbMATH Keywords: factorizations
zbMATH Keywords: cycle-systems
zbMATH Keywords: Hamilton-Waterloo problem
zbMATH Keywords: Oberwolfach problem
reviewed by: Ratnakaram Nava Mohan
MaRDI profile type: Publication
full work available at URL: s003730200001
OpenAlex ID: W2092787561
DOI: 10.1007/S003730200001
description: scientific article; zbMATH DE number 1740502