Graph powers and k-ordered Hamiltonicity

It is known that if G   is a connected simple graph, then G3G3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k  -ordered Hamiltonian if for any sequence v1v1, v2,…,vkv2,…,vk of k   vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k⩾4k⩾4, then G⌊3k/2⌋-2G⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k   vertices. By considering the case of the path graph PnPn, we show that this result is sharp. We also give a lower bound on the power of the cycle CnCn that guarantees k-ordered Hamiltonicity.