New Conditions for $k$-ordered Hamiltonian Graphs

Abstract

We show that in any graph $G$ on $n$ vertices with $d(x)+d(y)\ge 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)\ge 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.