Sectionable terraces and the (generalised) Oberwolfach problem (Q1810660)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sectionable terraces and the (generalised) Oberwolfach problem |
scientific article |
Statements
Sectionable terraces and the (generalised) Oberwolfach problem (English)
0 references
9 June 2003
0 references
In 1892 Lucas posed (and solved, giving credit to Walecki) the round-dance problem of arranging an odd number \(v\) of children to dance in \((v-1)/2\) successive rings, each of size \(v\), in such a way that each child has every other child as a neighbor exactly once. The Oberwolfach problem, due to Ringel, requires an odd number \(v\) of people to dine at a set of round tables of individual capacity at least 3 and total capacity \(v\) for \((v-1)/2\) successive meals in such a way that each person has every other person as a neighbor exactly once. Both problems are equivalent to decomposing the complete graph \(K_v\) on the vertices into mutually isomorphic 2-factors---the round-dance problem requires that the 2-factors are Hamiltonian cycles, whereas in the Oberwolfach problem each 2-factor must be a union of cycles where the sum of the lengths of the cycles is \(v\). In the literature the problem has been denoted by \(\text{OP}(l_1,\dots,l_m)\), where there are \(m\) cycles of the lengths \(l_1,l_2,\dots, l_m\). \textit{P. Gvozdjak} [Discrete Math. 173, 61-69 (1997; Zbl 0908.05073)] considered the more general problem of decomposing the complete multigraph \(\lambda K_{n+1}\) into mutually isomorphic 2-factors---here \(n+1\) may be even or odd provided that, if \(n+1\) is even, then so is \(\lambda\). The generalized Oberwolfach problem requires \(v\) people to sit at \(s\) round tables of sizes \(l_1,\dots, l_s\) (where \(l_1+l_2+\cdots+ l_s= v\)) for successive meals in such a way that each pair of people are neighbors exactly \(\lambda\) times. The problem has been denoted by \(\text{OP}(\lambda; l_1,l_2,\dots, l_m)\), and if \(\lambda= 1\), which turns out to be the original problem, which has been abbreviated to \(\text{OP}(l_1,l_2,\dots, l_m)\). Even though it was well known in 1892 a different terminology was used then, but that a directed terrace with a symmetric sequencing for the cycle group of order \(2n\) can be used to solve \(\text{OP}(2n+1)\). In this paper the authors showed that how terraces with special properties can be used to solve \(\text{OP}(2;l_1,l_2)\) and \(\text{OP}(l_1,l_1,l_2)\) for a wide selection of values of \(l_1\), \(l_2\) and \(v\). They also gave a new solution to \(\text{OP}(2;l,l)\) that is based on \(Z_{2l-1}\). Solutions to the problem are also of use in the design of experiments, where solutions for tables of equal size are called resolvable balanced circuit Rees neighbor designs.
0 references
2-sequencing
0 references
terrace
0 references
Hamiltonian decomposition
0 references
Lucas-Walecki construction
0 references
circuit Rees neighbour design
0 references
round-dance neighbur design
0 references
symmetric sequencing
0 references
0 references