Hyper-Hamiltonian circulants

Zbigniew R. Bogdanowicz (US Army, CCDC Armaments Center, Picatinny, New Jersey 07806, USA)

Electronic Journal of Graph Theory and Applications (EJGTA)
Vol 9, No 1 (2021): Electronic Journal of Graph Theory and Applications

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.