Hamiltonian Square-Paths

A hamiltonian square-path (-cycle) is one obtained from a hamiltonian path (cycle) by joining every pair of vertices of distance two in the path (cycle). LetGbe a graph onnvertices with minimum degreeδ(G). Posá and Seymour conjectured that ifδ(G)⩾23n, thenGcontains a hamiltonian square-cycle. We prove that ifδ(G)⩾(2n−1)/3, thenGcontains a hamiltonian square-path. A consequence of this result is a theorem of Aigner and Brandt that confirms the caseΔ(H)=2 of the Bollabás–Eldridge Conjecture: ifGandHare graphs onnvertices and (Δ(G)+1)(Δ(H)+1)⩽n+1, thenGandHcan be packed.