Linkedness and Ordered Cycles in Digraphs
Daniela Kühn, Deryk Osthus · Combinatorics Probability Computing · 2007
Given a digraphD, let δ0(D) := min{δ+(D), δ−(D)} be the minimum semi-degree ofD. We show that every sufficiently large digraphDwith δ0(D)≥n/2 +l−1 isl-linked. The bound on the minimum semi-degree is best possible and confirms a conjecture of Manoussakis [17]. We also determine the smallest minimum semi-degree which ensures that a sufficiently large digraphDisk-ordered,i.e., that for every sequences1, . . .,skof distinct vertices ofDthere is a directed cycle which encounterss1, . . .,skin this order. This result will be used in [16].