Global cycle properties of locally isometric graphs

Let PP be a graph property. A graph GG is said to be locally  PP if the subgraph induced by the open neighbourhood of every vertex in GG has property PP. Ryjáček’s well-known conjecture that every connected, locally connected graph is weakly pancyclic motivated us to consider the global cycle structure of locally PP graphs, where PP is the property of having diameter at most kk for some fixed k≥1k≥1. For k=2k=2 these graphs are called locally isometric graphs  . For Δ≤5Δ≤5, we obtain a complete structural characterization of locally isometric graphs that are not fully cycle extendable. For Δ=6Δ=6, it is shown that locally isometric graphs that are not fully cycle extendable contain a pair of true twins of degree 6. Infinite classes of locally isometric graphs with Δ=6Δ=6 that are not fully cycle extendable are described and observations are made that suggest that a complete characterization of these graphs is unlikely. It is shown that Ryjáček’s conjecture holds for all locally isometric graphs with Δ≤6Δ≤6. The Hamilton cycle problem for locally isometric graphs with maximum degree at most 8 is shown to be NP-complete.