Hamiltonian Cycles in \(N^2\)-Locally Connected Claw-Free Graphs

Abstract

For a vertex \(v\) in a graph \(G\), we denote by \(N^2(v)\) the set \((N_1(N_1(v))\setminus \{v\})\cup N_1(v)=\{x\in V(G): 1 \leq d(x,v) \leq 2\}\), where \(d(x,v)\) denotes the distance between \(x\) and \(v\). A vertex \(v\) is \(N^2\)-locally connected if the subgraph induced by \(N^2(v)\) is connected. A graph \(G\) is called \(N^2\)-locally connected if every vertex of \(G\) is \(N^2\)-connected. A well-known result by Oberly and Sumner is that every connected locally connected claw-free graph on at least three vertices is Hamiltonian. This result was improved by Ryjacek using the concept of second-type neighborhood. In this paper, using the concept of \(N^2\)-locally connectedness, we show that every connected \(N^2\)-locally connected claw-free graph \(G\) without vertices of degree \(1\), which does not contain an induced subgraph \(H\) isomorphic to one of \(G_1, G_2, G_3\), or \(G_4\), is Hamiltonian, hereby generalizing the result of Oberly and Sumner (J. Graph Theory, \(3 (1979) 351-356\))and the result of \(Ryjacek\)( J. Graph Theory, \(14 (1990)\) 321-381)