Hamiltonian Cycle Systems Which Are Both Cyclic and Symmetric

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.