The square of paths and cycles (Q1892831)

The square of a cycle (path) is the graph obtained by joining every pair of vertices of distance two in the cycle (path). Posa conjectured that if a graph \(G\) on \(n\) vertices has minimum degree \(\delta(G)\) at least \({2\over 3}n\), then \(G\) contains the square of a Hamiltonian cycle. The main result shown here is the following: Let \(G\) be a graph on \(n\) vertices. For any \(\varepsilon> 0\), there exists a number \(m\), depending only on \(\varepsilon\), such that if \(\delta(G)\geq ({2\over 3}+ \varepsilon) n+ m\), then any two independent edges in \(G\) are joined by the square of a Hamiltonian path in \(G\). Consequently, such \(G\) contains the square of a Hamiltonian cycle. The proof uses a lemma of Häggkvist on 3-partitioning the vertices of a graph.