Hamiltonicity, neighborhood intersections and the partially square graphs (Q5957758)

A partially square graph \(G^*\) of \(G\) is obtained from \(G\) by adding edges \(\{u,v\}\) whenever there exists a common neighbor \(w\) of \(u\) and \(v\) satisfying \(N(w)\subseteq N(u)\cup N(v)\cup\{u,v\}\). \textit{A.~Ainouche} and \textit{M.~Kouider} [Graphs Comb. 15, 257-265 (1999; Zbl 0933.05096)] showed that an \(l\)-connected (\(l=k,k-1,k+1\) for \(k\geq 2\)) graph \(G\) is Hamiltonian, traceable, 1-Hamiltonian and Hamitonian-connected provided \(\alpha(G^*)\leq k\). The authors of the paper under review prove that the last inequality can be replaced by weaker sufficient conditions expressed as weighted sums of sizes of neighborhood intersections in \(G\) of independent sets in \(G^*\). Their proof adopts the technique of vertex insertion.