On the honeymoon Oberwolfach problem. Issue 7 (5th April 2019)

• Record Type: Journal Article
• Authors: Lepine, Dene; Šajna, Mateja
• Is Part Of: Journal of combinatorial designs. Volume 27:Issue 7(2019:Jul.)
• Page Start: 420
• Page End: 447
• Publication Date: 2019-04-05
• Subjects: 2‐factorization -- honeymoon Oberwolfach problem -- Oberwolfach problem -- resolvable cycle decomposition -- semiuniform 1‐factorization; Combinatorial designs and configurations -- Periodicals; Configurations et schémas combinatoires -- Périodiques; 511.6
• DOI: 10.1002/jcd.21656
• Languages: English
• ISSNs: 1063-8539

Abstract

Abstract: The honeymoon Oberwolfach problem HOP ( 2 m 1, 2 m 2, …, 2 m t ) asks the following question. Given n = m 1 + m 2 + ⋯ + m t newlywed couples at a conference and t round tables of sizes 2 m 1, 2 m 2, …, 2 m t, is it possible to arrange the 2 n participants at these tables for 2 n − 2 meals so that each participant sits next to their spouse at every meal and sits next to every other participant exactly once? A solution to HOP ( 2 m 1, 2 m 2, …, 2 m t ) is a decomposition of K 2 n + ( 2 n − 3 ) I, the complete graph K 2 n with 2 n − 3 additional copies of a fixed 1‐factor I, into 2‐factors, each consisting of disjoint I ‐alternating cycles of lengths 2 m 1, 2 m 2, …, 2 m t . It is also equivalent to a semi‐uniform 1‐factorization of K 2 n of type ( 2 m 1, 2 m 2, …, 2 m t ) ; that is, a 1‐factorization { F 1, F 2, …, F 2 n − 1 } such that for all i ≠ 1, the 2‐factor F 1 ∪ F i consists of disjoint cycles of lengths 2 m 1, 2 m 2, …, 2 m t . In this paper, we first introduce the honeymoon Oberwolfach problem and then present several results. Most notably, we completely solve the case with uniform cycle lengths, that is, HOP ( 2 m, 2 m, …, 2 m ) . In addition, we show that HOP ( 2 m 1, 2 m 2, …, 2 m t ) has a solution in each of the following cases: n ≤ 9 ; n is odd and t = 2 ; as well as m i ≡ 0 ( mod 4 ) for all i . We also show that HOP ( 2 m 1, 2 m 2, …, 2 m t ) has a solution whenever n is odd and the Oberwolfach problem with tables of sizes m 1, m 2, …, m t has a solution.