Forbidden Subgraphs for a Graph to Have a Hamiltonian Path Square

The square of a graph is obtained by adding an edge between each pair of vertices that are of distance 2 in the original graph. If a graph G has a hamiltonian path (or cycle) square, then the square of the hamiltonian path (or cycle) is called a hamiltonian path (or cycle) square of G. Chen and Shan (Graphs Comb 31:2113–2124, 2015) characterized all forbidden pairs for a 4-connected graph to have a hamiltonian cycle square. In this paper, we completely characterize pairs of connected forbidden subgraphs for a k-connected (k∈ { 1 , 2 , 3 , 4 }) graph with maximal degree at least 4 to have a hamiltonian path square. Note that the maximal degree condition is necessary for graphs of order at least 5 to have a hamiltonian path square.