Every 1-rotational solution of a classic or twofold Oberwolfach problem (OP) of order n is generated by a suitable 2-factor (starter) of $K_n$ or $2K_n$, respectively. It is shown that any starter of a twofold OP of order n gives rise to a starter of a classic OP of order 2n-1 (doubling construction). It is also shown that by suitably modifying the starter of a classic OP, one may obtain starters of some other OPs of the same order but having different parameters. The combination of these two constructions leads to lots of new infinite classes of solvable OPs. Still more classes can be obtained with the help of a third construction making use of the possible gracefulness of a graph whose connected components are cycles and at most one path. As one of the many applications, Hilton and Johnson's [J London Math Soc, 64 (2001) 513–522] bound $s\geq 5r-1$ about the solvability of OP(r,s) is improved to $s \geq \lfloor r/4 \rfloor + 10$ in the case of r even.

2-starters, graceful labelings, and a doubling construction for the Oberwolfach Problem

BURATTI, Marco;
2012

Abstract

Every 1-rotational solution of a classic or twofold Oberwolfach problem (OP) of order n is generated by a suitable 2-factor (starter) of $K_n$ or $2K_n$, respectively. It is shown that any starter of a twofold OP of order n gives rise to a starter of a classic OP of order 2n-1 (doubling construction). It is also shown that by suitably modifying the starter of a classic OP, one may obtain starters of some other OPs of the same order but having different parameters. The combination of these two constructions leads to lots of new infinite classes of solvable OPs. Still more classes can be obtained with the help of a third construction making use of the possible gracefulness of a graph whose connected components are cycles and at most one path. As one of the many applications, Hilton and Johnson's [J London Math Soc, 64 (2001) 513–522] bound $s\geq 5r-1$ about the solvability of OP(r,s) is improved to $s \geq \lfloor r/4 \rfloor + 10$ in the case of r even.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/659497
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 16
  • ???jsp.display-item.citation.isi??? 16
social impact