Square Hamiltonian cycles in graphs with maximal 4-cliques
Seymour conjectured that if \(G\) is a graph of order \(n\) with minimum degree at least \(kn/(k+1)\), then \(G\) contains the \(k\)th power of a Hamiltonian cycle. The special case when \(k = 2\) was conjectured earlier by Pósa. In the case when the graph \(G\) contains a maximal \(4\)-clique, the conjecture of Pósa is verified (e.g. if \(G\) has minimal degree at least \(2n/3\) and a maximal \(4\)-clique, then \(G\) has the square of a Hamiltonian cycle). An asymptotic version of the conjecture of Pósa has been proved by Komol'os, Sárkőzy, and Szemerédi, but is not yet in print.
scientific article; zbMATH DE number 1110096