Abstract. The minimum semi-degree of a digraph D is the minimum of its minimum
outdegree and its minimum indegree. We show that every sufficiently large
digraph D with minimum semi-degree at least n/2 +k-1 is k-linked. The bound on
the minimum semi-degree is best possible and confirms a conjecture of
Manoussakis from 1990. We also determine the smallest minimum semi-degree which
ensures that a sufficiently large digraph D is k-ordered, i.e. that for every
ordered sequence of k distinct vertices of D there is a directed cycle which
encounters these vertices in this order.
There are no comments yet.