Advanced Search

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 $N_G\left(x\right)\subseteq N_G\left[u\right]\cup N_G\left[v\right]$, where $N_G\left[x\right]=N_G\left(x\right)\cup x$. In particular, this condition is satisfied if x does not center a claw (an induced $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...