On the Generalized Honeymoon Oberwolfach Problem

Abstract

The Honeymoon Oberwolfach Problem (HOP), introduced by Šajna, is a recent variant of the classic Oberwolfach Problem. This problem asks whether it is possible to seat 2m₁ + 2m₂ + · · · + 2mₜ = 2n participants, consisting of n newlywed couples, at t round tables of sizes 2m₁, 2m₂, . . . , 2mₜ for 2n - 2 successive nights, so that each participant sits next to their spouse every night and next to every other participant exactly once. This problem is denoted by HOP(2m₁, 2m₂, . . . , 2mₜ). Jerade, Lepine, and Šajna have studied the HOP and resolved several important cases.

In this thesis, we generalize the HOP by allowing tables of size two, relaxing the previous restriction that tables must have a minimum size of four. In the generalized HOP, we aim to seat the 2n participants at s tables of size 2 and t round tables of sizes 2m₁, 2m₂, . . . , 2mₜ, where 2n = 2s + 2m₁ + 2m₂ + · · · + 2mₜ and mᵢ ≥ 2, while preserving the original adjacency conditions of the HOP. We denote this problem by HOP(2⁽ˢ⁾, 2m₁, . . . , 2mₜ).

We present a general approach to this problem and provide solutions to several cases. In particular, we present partial results on the generalized HOP with two round tables, showing that a solution to HOP(2⁽ˢ⁾, 2m₁, 2m₂) exists when n ≡ 1 (mod 2m₁ + 2m₂) and when n ≡ m₁ + m₂ (mod 2m₁ + 2m₂). We also develop solutions for cases with small round tables, showing that HOP(2⁽ˢ⁾, 2m₁, . . . , 2mₜ) has a solution for all m = m₁ + · · · + mₜ ≤ 10 whenever n = s + m is odd and n(n - 1) ≡ 0 (mod 2m). Lastly, we establish a complete solution to the generalized HOP with a single round table, demonstrating that the necessary condition for HOP(2⁽ˢ⁾, 2m) to have a solution is also sufficient.