The existence problem for a Hamiltonian cycle decomposition of $K_{2n} − 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 $\ell$ such that p ≡ 1 (mod $2^\ell$) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that $p \not\equiv 1$ (mod $2^{\ell+1}$) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k 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 of $K_{2n}-I$ if and only if n≡2 (mod 4).

Dihedral Hamiltonian cycle systems of the cocktail party graph / Buratti, Marco; F., Merola. - In: JOURNAL OF COMBINATORIAL DESIGNS. - ISSN 1063-8539. - 21:1(2013), pp. 1-23. [10.1002/jcd.21311]

Dihedral Hamiltonian cycle systems of the cocktail party graph

BURATTI, Marco;
2013

Abstract

The existence problem for a Hamiltonian cycle decomposition of $K_{2n} − 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 $\ell$ such that p ≡ 1 (mod $2^\ell$) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that $p \not\equiv 1$ (mod $2^{\ell+1}$) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k 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 of $K_{2n}-I$ if and only if n≡2 (mod 4).
2013
Hamiltonian cycle system; Cocktail party graph; dihedral group
01 Pubblicazione su rivista::01a Articolo in rivista
Dihedral Hamiltonian cycle systems of the cocktail party graph / Buratti, Marco; F., Merola. - In: JOURNAL OF COMBINATORIAL DESIGNS. - ISSN 1063-8539. - 21:1(2013), pp. 1-23. [10.1002/jcd.21311]
File allegati a 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/11573/1654656
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 23
  • ???jsp.display-item.citation.isi??? 22
social impact