Preskoči na glavno vsebino

Maruša Lekše: The spouse loving variant of the Oberwolfach problem

Datum objave: 17. 11. 2023
Seminar za diskretno matematiko
Plemljev seminar, Jadranska 19


The Oberwolfach problem asks the following: given a 2-factor F of the complete graph Kn, does there exist a decomposition of Kn into graphs isomorphic to F? It was asked by Gerhard Ringel in 1967, and it models a situation where the participants at a conference are having dinner together every evening in a room with round tables of different sizes, and they want to find a seating arrangement such that over an appropriate amount of meals, every participant sits next to every other participant exactly once. A lot of results have been obtained on this problem and its variants, but in general it is still unsolved. In this talk we will focus on the spouse loving variant of the problem, in which we are looking for decompositions of a complete graph with the edges of a 1-factor duplicated.