Premium
Dihedral Hamiltonian Cycle Systems of the Cocktail Party Graph
Author(s) -
Buratti Marco,
Merola Francesca
Publication year - 2013
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.21311
Subject(s) - dihedral angle , mathematics , dihedral group , hamiltonian path , hamiltonian (control theory) , combinatorics , graph , discrete mathematics , group (periodic table) , quantum mechanics , physics , mathematical optimization , hydrogen bond , molecule
The existence problem for a Hamiltonian cycle decomposition ofK 2 n − I (the so called cocktail party graph ) with a dihedral automorphism group acting sharply transitively on the vertices is completely solved. Such Hamiltonian cycle decompositions exist for all even n while, for n odd, they exist if and only if the following conditions hold: (i) n is not a prime power; (ii) there is a suitable ℓ such that p ≡ 1 (mod 2 ℓ ) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that p ¬ ≡ 1 (mod 2 ℓ + 1 ) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8 k vertices for all k , while it is known that no such cyclic Hamiltonian cycle decomposition exists. Finally, this paper touches on a recently introduced symmetry requirement by proving that there exists a dihedral and symmetric Hamiltonian cycle system ofK 2 n − I if and only if n ≡ 2 (mod 4).