Hamiltonicity, neighborhood intersections and the partially square graphs Original Research Article

Let G be a graph. The partially square graph G∗ of G is a graph obtained from G by adding edges uv satisfying the conditions uv∉E(G), and there is some w∈N(u)∩N(v), such that N(w)⊆N(u)∪N(v)∪{u,v}. A non-negative rational sequence (a1,a2,…,ak+1) is called an LTW-sequence if the following conditions are satisfied: (1) a1⩽1; (2) for arbitrary i1,i2,…,ih∈{2,3,…,k+1},∑j=1hij⩽k+1 implies ∑j=1h(aij−1)⩽1. In this paper, we will use the technique of the vertex insertion on l-connected (l=k,k−1 or k+1,k⩾2) graphs to provide a unified proof for G to be hamiltonian, traceable, 1-hamiltonian or hamiltonian-connected, the sufficient conditions are expressed by weighted sums of the neighborhood intersections in G of independent sets in G∗, where the weights are LTW-sequences.