首页|On Hamiltonicity of regular graphs with bounded second neighborhoods
On Hamiltonicity of regular graphs with bounded second neighborhoods
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
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 is an element of G(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 is an element of G(k), k >= 6, is Hamiltonian and that for each non-Hamiltonian cycle C in G there exists a cycle C' of length vertical bar V(C)vertical bar + l in G, l is an element of {1, 2}, such that V(C) subset of V(C'). Finally, we note that all our conditions for Hamiltonicity apply to infinitely many graphs with large diameters. (C) 2022 The Authors. Published by Elsevier B.V.
NSTL
Elsevier
