2007/07/11 by Daniela Kühn, Kühn, Daniela, Deryk Osthus +3 · 1 citation
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.0707.1577
Given a digraph D, the minimum semi-degree of D is the minimum of its minimum indegree and its minimum outdegree. D is k-ordered Hamiltonian if for every ordered sequence of k distinct vertices there is a directed Hamilton cycle which encounters these vertices in this order. Our main result is that every digraph D of sufficiently large order n with minimum semi-degree at least (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.