Premium
1‐rotational k ‐factorizations of the complete graph and new solutions to the Oberwolfach problem
Author(s) -
Buratti Marco,
Rinaldi Gloria
Publication year - 2008
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.20163
Subject(s) - mathematics , dihedral group , combinatorics , conjugacy class , vertex (graph theory) , factorization , pairwise comparison , digraph , graph , group (periodic table) , symmetric group , discrete mathematics , algorithm , chemistry , statistics , organic chemistry
We consider k ‐factorizations of the complete graph that are 1‐ rotational under an assigned group G , namely that admit G as an automorphism group acting sharply transitively on all but one vertex. After proving that the k ‐factors of such a factorization are pairwise isomorphic, we focus our attention to the special case of k = 2, a case in which we prove that the involutions of G necessarily form a unique conjugacy class. We completely characterize, in particular, the 2‐factorizations that are 1‐rotational under a dihedral group. Finally, we get infinite new classes of previously unknown solutions to the Oberwolfach problem via some direct and recursive constructions. © 2007 Wiley Periodicals, Inc. J Combin Designs 16: 87–100, 2008