On $k$-ordered Hamiltonian Graphs

Abstract

A Hamiltonian graph $G$ of order $n$ is $k$-ordered, $2\le k\le n$, if for every sequence $v_1,v_2,\dots ,v_k$ of $k$ distinct vertices of $G$, there exists a Hamiltonian cycle that encounters $v_1,v_2,\dots ,v_k$ in this order. In this paper, answering a question of Ng and Schultz, we give a sharp bound for the minimum degree guaranteeing that a graph is a $k$-ordered Hamiltonian graph under some mild restrictions. More precisely, we show that there are $\epsilon ,n_0>0$ such that if $G$ is a graph of order $n\ge n_0$ with minimum degree at least $\lceil \frac{n}{2}\rceil +\lfloor \frac{k}{2}\rfloor -1$ and $2\leq k \leq \eps n$, then $G$ is a $k$-ordered Hamiltonian graph. It is also shown that this bound is sharp for every $2\le k\le \lfloor \frac{n}{2}\rfloor$.