k-Ordered Hamilton cycles in digraphs

Given a digraph D. let delta(0)(D) := min{delta(+)(D), delta(-)(D)} be the minimum semi-degree of D. D is k-ordered Hamiltonian if for every sequence s(l).....s(k) of distinct vertices of D there is a directed Hamilton cycle which encounters s(l.).....s(k) in this order. Our main result is that every digraph D of sufficiently large order n with delta(0)(D) >= [(n + k)/2] - I is k-ordered Hamiltonian. The bound oil the minimum semi-degree is best possible. An undirected version of this result was proved earlier by Kierstead, Sarkozy and Selkow [H. Kierstead. G. Sarkozy. S. Selkow, On k-ordered Hamiltonian graphs, J. Graph Theory 32 (1999) 17-25]. (c) 2008 Elsevier Inc. All rights reserved.