Premium
2‐Starters, Graceful Labelings, and a Doubling Construction for the Oberwolfach Problem
Author(s) -
Buratti Marco,
Traetta Tommaso
Publication year - 2012
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21296
Subject(s) - mathematics , combinatorics , starter , order (exchange) , graph , path (computing) , discrete mathematics , computer science , finance , automotive engineering , engineering , economics , programming language
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 2 K 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 2 n − 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 ≥ 5 r − 1 about the solvability of OP ( r , s ) is improved to s ≥ ⌊ r / 4 ⌋ + 10 in the case of r even. © 2012 Wiley Periodicals, Inc. J. Combin. Designs 20: 483‐503, 2012