2007/04/02 by Daniela Kühn, Kühn, Daniela, Deryk Osthus +1
Mathematics · #05C20 #05C35 #05C40 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C20 #msc:05C35 #msc:05C40
paper · pdf · doi:10.48550/arxiv.0704.0211
arxiv created 2007/04/02 · arxiv updated 2009/12/01
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.