k-Ordered Hamilton cycles in digraphs

Given a digraph D, let δ 0 ( D ) : = min { δ + ( D ) , δ − ( D ) } be the minimum semi-degree of D. D is k-ordered Hamiltonian if for every sequence s 1 , … , s k of distinct vertices of D there is a directed Hamilton cycle which encounters s 1 , … , s k in this order. Our main result is that every digraph D of sufficiently large order n with δ 0 ( D ) ⩾ ⌈ ( n + k ) / 2 ⌉ − 1 is k-ordered Hamiltonian. The bound on the minimum semi-degree is best possible. An undirected version of this result was proved earlier by Kierstead, Sárközy and Selkow [H. Kierstead, G. Sárközy, S. Selkow, On k-ordered Hamiltonian graphs, J. Graph Theory 32 (1999) 17–25].