Nested Locally Hamiltonian Graphs and the Oberly-Sumner Conjecture

A graph G is locally P, abbreviated LP, if for every vertex v in G the open neighbourhood N(v) of v is non-empty and induces a graph with property P. Specifically, a graph G without isolated vertices is locally connected (LC) if N(v) induces a connected graph for each v is an element of V (G), and locally hamiltonian (LH) if N(v) induces a hamiltonian graph for each v is an element of V (G). A graph G is locally locally P (abbreviated (LP)-P-2) if N(v) is non-empty and induces a locally P graph for every v is an element of V (G). This concept is generalized to an arbitrary degree of nesting. For any k 0 we call a graph locally k-nested-hamiltonian if it is (LC)-C-m for m = 0, 1, . . ., k and (LH)-H-k (with (LC)-C-0 and (LH)-H-0 meaning connected and hamiltonian, respectively). The class of locally k-nested-hamiltonian graphs contains important subclasses. For example, Skupien had already observed in 1963 that the class of connected LH graphs (which is the class of locally 1-nested-hamiltonian graphs) contains all triangulations of closed surfaces. We show that for any k >= 1 the class of locally k-nested-hamiltonian graphs contains all simple-clique (k + 2)-trees. In 1979 Oberly and Sumner proved that every connected K-1,K-3-free graph that is locally connected is hamiltonian. They conjectured that for k >= 1, every connected K-1,(k)+3-free graph that is locally (k + 1)-connected is hamiltonian. We show that locally k-nested-hamiltonian graphs are locally (k + 1)-connected and consider the weaker conjecture that every K-1,(k)+3-free graph that is locally k-nested-hamiltonian is hamiltonian. We show that if our conjecture is true, it would be "best possible" in the sense that for every k >= 1 there exist K-1,(k)+4-free locally k-nested-hamiltonian graphs that are non-hamiltonian. We also attempt to determine the minimum order of non-hamiltonian locally k-nested-hamiltonian graphs and investigate the complexity of the Hamilton Cycle Problem for locally k-nested-hamiltonian graphs with restricted maximum degree.