Graphs with Hamiltonian balls
Armen S. Asratian, Natalia Oksimets · 1998
For a vertex u of a graph G and an integer r, the ball of radius r centered at u is the subgraph Gr(u) induced by the set of all vertices of G whose distance from u does not exceed r. We investigate the set 1i of connected graphs G with at least 3 vertices such that every ball of radius 1 in G has a Hamilton cycle. We prove that every graph G in 1- £ with n vertices has at least 2n- 3 edges, and every such graph with 2n- 3 edges is isomorphic to a triangulation of a polygon. We show that some well-known conditions for hamiltonicity of a graph G also guarantee that G has the following property: for each vertex u of G and each integer r 2:: 1, the ball Gr(u) has a Hamilton cycle. 1.