Premium
Hamiltonian Cycle Systems Which Are Both Cyclic and Symmetric
Author(s) -
Buratti Marco,
Merola Francesca
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.21351
Subject(s) - combinatorics , mathematics , multigraph , vertex (graph theory) , permutation (music) , hamiltonian path , invariant (physics) , graph , discrete mathematics , physics , mathematical physics , acoustics
The notion of a symmetric Hamiltonian cycle system (HCS) of a graph Γ has been introduced and studied by J. Akiyama, M. Kobayashi, and G. Nakamura [J Combin Des 12 (2004), 39–45] for Γ = K v , by R. A. Brualdi and M. W. Schroeder [J Combin Des 19 (2011), 1–15] for Γ = K v − I , and then naturally extended by V. Chitra and A. Muthusamy [Discussiones Mathematicae Graph Theory, to appear] to the multigraphs Γ = λ K vand Γ = λ K v − I . In each case, there must be an involutory permutation ψ of the vertices fixing all the cycles of the HCS and at most one vertex. Furthermore, for Γ = λ K v − I , this ψ 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 ofK v − I has been completely solved by Jordon and Morris [Discrete Math (2008), 2440–2449]—and we note that their cyclic construction is also symmetric for v ≡ 4 (mod 8). It is then natural to study the existence problem of an HCS of a graph or multigraph Γ 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 λ K 2 n + 1with both properties exists if and only if 2 n + 1 is a prime.