On the Hamilton-Waterloo problem (Q1348664)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the Hamilton-Waterloo problem |
scientific article |
Statements
On the Hamilton-Waterloo problem (English)
0 references
14 May 2002
0 references
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)\}\).
0 references
decomposition
0 references
factorizations
0 references
cycle-systems
0 references
Hamilton-Waterloo problem
0 references
Oberwolfach problem
0 references