New Conditions for \(k\)-ordered Hamiltonian Graphs

Abstract

We show that in any graph \(G\) on \(n\) vertices with \(d(x) + d(y) \geq n\) for any two nonadjacent vertices \(x\) and \(y\), we can fix the order of \(k\) vertices on a given cycle and find a Hamiltonian cycle encountering these vertices in the same order, as long as \(k < n/12\) and \(G\) is \([(k+1)/2]\)-connected. Further, we show that every \([3k/2]\)-connected graph on \(n\) vertices with \(d(x) + d(y) \geq n\) for any two nonadjacent vertices \(x\) and \(y\) is \(k\)-ordered Hamiltonian, i.e., for every ordered set of \(k\) vertices, we can find a Hamiltonian cycle encountering these vertices in the given order. Both connectivity bounds are best possible.