Premium
Some Results on 1‐Rotational Hamiltonian Cycle Systems
Author(s) -
Buratti Marco,
Rinaldi Gloria,
Traetta Tommaso
Publication year - 2014
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.21352
Subject(s) - mathematics , combinatorics , isomorphism (crystallography) , automorphism , hamiltonian (control theory) , automorphism group , hamiltonian path , vertex (graph theory) , rotational symmetry , discrete mathematics , graph , crystallography , geometry , mathematical optimization , chemistry , crystal structure
A Hamiltonian cycle system of K v (briefly, a HCS( v )) is 1‐ rotational under a (necessarily binary ) group G if it admits G as an automorphism group acting sharply transitively on all but one vertex. We first prove that for any n ≥ 3 there exists a 3‐perfect 1‐rotational HCS ( 2 n + 1 ) . This allows to get the existence of another infinite class of 3‐perfect (but not Hamiltonian) cycle decompositions of the complete graph. Then we prove that the full automorphism group of a 1‐rotational HCS under G is G itself unless the HCS is the 2‐transitive one. This allows us to give a partial answer to the problem of determining which abstract groups are the full automorphism group of a HCS. Finally, we revisit and simplify by means of a careful group theoretic discussion a formula by Bailey, Ollis, and Preece on the number of inequivalent 1‐rotational HCSs under G . This leads us to a formula counting all 1‐rotational HCSs up to isomorphism. Though this formula heavily depends on some parameters that are hard to compute, it allows us to say that, for any n ≥ 6 , there are at least 2 ⌈ 3 n / 4 ⌉nonisomorphic 1‐rotational (and hence symmetric) HCS( 2 n + 1 ).