Variations on a sufficient condition for Hamiltonian graphs

Given a 2-connected graph G on n vertices, let G* be its partially square graph, obtained by adding edges uv whenever the vertices u,v have a common neighbor x satisfying the condition ${\displaystyle N_G\left(x\right)\subseteq N_G\left[u\right]\cup N_G\left[v\right]}$, where ${\displaystyle N_G\left[x\right]=N_G\left(x\right)\cup \left\{x\right\}}$. In particular, this condition is satisfied if x does not center a claw (an induced ${\displaystyle K_{1,3}}$). Clearly G ⊆ G* ⊆ G², where G² is the square of G. For any independent triple X = {x,y,z} we define σ̅(X) = d(x) + d(y) + d(z) - |N(x) ∩ N(y) ∩ N(z)|. Flandrin et al. proved that a 2-connected graph G is hamiltonian if [σ̅]₃(X) ≥ n holds for any independent triple X in G. Replacing X in G by X in the larger graph G*, Wu et al. improved recently this result. In this paper we characterize the nonhamiltonian 2-connected graphs G satisfying the condition [σ̅]₃(X) ≥ n-1 where X is independent in G*. Using the concept of dual closure we (i) give a short proof of the above results and (ii) we show that each graph G satisfying this condition is hamiltonian if and only if its dual closure does not belong to two well defined exceptional classes of graphs. This implies that it takes a polynomial time to check the nonhamiltonicity or the hamiltonicity of such G.