ON k-ORDERED HAMILTONIAN GRAPHS

GABOR N. SARKOZY STANLEY SELKOW

Abstract. A Hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v_{1}, v_{2}, …, v_{k} of k distinct vertices of G, there exists a Hamiltonian cycle that encounters v_{1}, v_{2}, …, 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 ε, n_{0} > 0 such that if G is a graph of order n ≥ n_{0} with minimum degree at least ⌈\frac{n}{2}⌉ + ⌊\frac{k}{2} ⌋ − 1 and 2 ≤ k ≤ εn, then G is a k-ordered Hamiltonian graph. It is also shown that this bound is sharp for every 2 ≤ k ≤ ⌊\frac{n}{2}⌋.