The Honeymoon Oberwolfach Problem: A Recursive Approach

Mary Rose Jerade, University of Ottawa

The Honeymoon Oberwolfach Problem (HOP) is a variant of the Oberwolfach Problem, which was first introduced by Mateja Šajna. The problem asks whether it is possible to seat n couples attending a conference for 2(n − 1) consecutive nights at l round tables of sizes 2m1, 2m2, . . . , 2ml such that mi ≥ 2 for all i = 1, . . . , l, Σ i=1 mi = 2n, and each participant must be seated next to their spouse every night, but next to each other person exactly once. This problem is denoted by HOP(2m1, 2m2, . . . , 2ml).

This seating arrangement problem smoothly translates into a graph theory problem. It is equivalent to finding a cycle decomposition of the graph K2n + (2n − 3)I (that is, the complete graph K2n with 2n − 3 additional copies of a fixed 1-factor I) into 2-factors such that each 2-factor consists of disjoint I-alternating cycles of lengths 2m1, . . . , 2ml. So far, solutions to HOP have been established for various cases, among which: for all n ≤ 20; when all tables are of the same size; when the table sizes are divisible by 8; and when n is odd and the Oberwolfach Problem OP(m1, . . . , ml) has a solution.

In this talk, we present a recursive approach to the problem. In particular, we show that if m1, . . . , ml are positive even integers, t is an integer such that &Sigma i=1 mi < t, and HOP(2m1, . . . , 2ml) has a solution, then HOP(2m1, . . . , 2ml, 2t) has a solution as well. Moreover, we will briefly touch on the case when m1, . . . , ml are not all even.

This is joint work with Mateja Šajna.