The notion of a symmetric Hamiltonian cycle system (HCS) of a graph Gamma has been introduced and studied by Akiyama, Kobayashi and Nakamura for Gamma=K_v, by Brualdi and Schroeder for Gamma=K_v-I, and then naturally extended by Chitra and Muthusamy to the multigraphs Gamma=\lambda K_v and Gamma=\lambda K_v-I. In each case there must be an involutory permutation \psi of the vertices fixing all the cycles of the HCS and at most one vertex. Furthermore, for Gamma=\lambda K_v_I, this \psi should be precisely the permutation switching all pairs of endpoints of the edges of I. An HCS is cyclic if it is invariant under some cyclic permutation of all the vertices. The existence question for a cyclic HCS of K_v-I has been completely solved by Jordon and Morris -- and we note that their cyclic construction is also symmetric for v\equiv4 (mod 8). It is then natural to study the existence problem of an HCS of a graph or multigraph Gamma as above which is both cyclic and symmetric. In this paper we completely solve this problem: in the case of even order, the final answer is that cyclicity and symmetry can always cohabit when a cyclic solution exists. On the other hand, imposing that a cyclic HCS of odd order is also symmetric is very restrictive; we prove in fact that an HCS of \lambda K_{2n+1} with both properties exists if and only if 2n+1 is a prime.

Marco Buratti, & Merola F (2014). Hamiltonian cycle systems which are both cyclic and symmetric. JOURNAL OF COMBINATORIAL DESIGNS, 22, 367-390 [10.1002/jcd.21351].

Hamiltonian cycle systems which are both cyclic and symmetric.

MEROLA, FRANCESCA
2014

Abstract

The notion of a symmetric Hamiltonian cycle system (HCS) of a graph Gamma has been introduced and studied by Akiyama, Kobayashi and Nakamura for Gamma=K_v, by Brualdi and Schroeder for Gamma=K_v-I, and then naturally extended by Chitra and Muthusamy to the multigraphs Gamma=\lambda K_v and Gamma=\lambda K_v-I. In each case there must be an involutory permutation \psi of the vertices fixing all the cycles of the HCS and at most one vertex. Furthermore, for Gamma=\lambda K_v_I, this \psi should be precisely the permutation switching all pairs of endpoints of the edges of I. An HCS is cyclic if it is invariant under some cyclic permutation of all the vertices. The existence question for a cyclic HCS of K_v-I has been completely solved by Jordon and Morris -- and we note that their cyclic construction is also symmetric for v\equiv4 (mod 8). It is then natural to study the existence problem of an HCS of a graph or multigraph Gamma as above which is both cyclic and symmetric. In this paper we completely solve this problem: in the case of even order, the final answer is that cyclicity and symmetry can always cohabit when a cyclic solution exists. On the other hand, imposing that a cyclic HCS of odd order is also symmetric is very restrictive; we prove in fact that an HCS of \lambda K_{2n+1} with both properties exists if and only if 2n+1 is a prime.
Marco Buratti, & Merola F (2014). Hamiltonian cycle systems which are both cyclic and symmetric. JOURNAL OF COMBINATORIAL DESIGNS, 22, 367-390 [10.1002/jcd.21351].
File in 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/11590/138545
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact