Hyper-Hamiltonian circulants
Abstract
A Hamiltonian graph G = (V,E) is called hyper-Hamiltonian if G-v is Hamiltonian for any v ∈ V(G). G is called a circulant if its automorphism group contains a |V(G)|-cycle. First, we give the necessary and sufficient conditions for any undirected connected circulant to be hyper-Hamiltonian. Second, we give necessary and sufficient conditions for a connected circulant digraph with two jumps to be hyper-Hamiltonian. In addition, we specify some sufficient conditions for a circulant digraph with arbitrary number of jumps to be hyper-Hamiltonian.
Keywords
Full Text:
PDFDOI: http://dx.doi.org/10.5614/ejgta.2021.9.1.16
References
T. Araki, Hyper hamiltonian laceability of Cayley graphs generated by transpositions, Networks, 48 (2006), 121–124.
F.T. Boesch and R. Tindell, Circulants and their connectivity, J. Graph Theory, 8 (1984), 129–138.
Z.R. Bogdanowicz, Isomorphism between circulants and Cartesian products of cycles, Discrete Applied Math., 226 (2017), 40–43.
Z.R. Bogdanowicz, Hamilton cycles in circulant digraphs with prescribed number of distinct jumps, Discrete Math., 309 (2009), 2100–2107.
Z.R. Bogdanowicz, Pancyclicity of connected circulant graphs, J. Graph Theory, 22 (1996), 167–174.
R.R. Del-Vecchio, C.T.M. Vinagre, and G.B. Pereira, Hyper-Hamiltonicity in graphs: some sufficient conditions, Elec. Notes Disc. Math., 62 (2017), 165–170.
L. Lovasz, Combinatorial problems and exercises, North-Holland, Amsterdam, 1979.
T. Mai, J. Wang, and L. Hsu, Hyper-Hamiltonian generalized Petersen graphs, Comput. and Math. with Appl., 55 (2008), 2076–2085.
A. Shabbir, Fault-tolerant designs in lattice networks on the Klein bottle, Electron. J. Graph Theory Appl., 2 (2) (2014), 99–109.
Refbacks
- There are currently no refbacks.
ISSN: 2338-2287
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.