2021/07/14 by Asratian, Armen S., Granholm, Jonas B.
#05C45 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2107.07037
Let G(k) denote the set of connected k-regular graphs G, k≥2, where the number of vertices at distance 2 from any vertex in G does not exceed k. Asratian (2006) showed (using other terminology) that a graph G\inG(k) is Hamiltonian if for each vertex u of G the subgraph induced by the set of vertices at distance at most 2 from u is 2-connected. We prove here that in fact all graphs in the sets G(3), G(4) and G(5) are Hamiltonian. We also prove that the problem of determining whether there exists a Hamilton cycle in a graph from G(6) is NP-complete. Nevertheless we show that every locally connected graph G\inG(k), k≥6, is Hamiltonian and that for each non-Hamiltonian cycle C in G there exists a cycle C' of length |V(C)|+ℓ in G, ℓ∈\1,2\, such that V(C)⊂ V(C'). Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters.