Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph (Q1817578)

The square of a graph \(G\) is the the graph with vertex set \(V(G)\) in which two vertices are adjacent if their distance in \(G\) is one or two. The graph \(S(K_{1,3})\) is the graph \(K_{1,3}\) in which each edge is subdivided once. The degree of a block \(B\) of a graph \(G\) is the number of cut vertices of \(G\) belonging to \(V(B)\). The paper proves that the square of a connected graph in which every induced \(S(K_{1,3})\) has at least three edges in a block of degree at most 2 is hamiltonian. It is also shown that insertion of a block of degree 2 into, or under certain conditions also deletion of such a block from, a connected graph does not change the hamiltonicity of the square of the graph.