Graph powers and \(k\)-ordered hamiltonicity (Q932592)

A simple graph \(G\) is \(k\)-ordered Hamiltonian if for any sequence \(v_1, v_2, \dots, v_k\) of \(k\) vertices of \(G\) there is a Hamiltonian cycle in \(G\) containing these vertices in the given order. Let \(H\) be a connected graph with at least \(k\) vertices, \(k \geq 4\). The author proves that \(H^{ \lfloor 3k/2 \rfloor - 2}\) is \(k\)-ordered Hamiltonian. The result is proved to be sharp by establishing a universal lower bound on the smallest power of the path that is \(k\)-ordered Hamiltonian. The k-ordered Hamiltonicity of powers of the cycle of \(n\) vertices is discussed.