TY - JOUR

T1 - Linkedness and Ordered Cycles in Digraphs

AU - Kuhn, Daniela

AU - Osthus, Deryk

PY - 2008/5/1

Y1 - 2008/5/1

N2 - Given a digraph D, let delta(0)(D) := min{delta(+)(D), delta(-)(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with delta(0)(D) >= n/2 + l - 1 is l-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 digraph D is k-ordered, i.e., that for every sequence s(1), ..., s(k) of distinct vertices of D there is a directed cycle which encounters s(1), ..., s(k) in this order. This result will be used in [16].

AB - Given a digraph D, let delta(0)(D) := min{delta(+)(D), delta(-)(D)} be the minimum semi-degree of D. We show that every sufficiently large digraph D with delta(0)(D) >= n/2 + l - 1 is l-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 digraph D is k-ordered, i.e., that for every sequence s(1), ..., s(k) of distinct vertices of D there is a directed cycle which encounters s(1), ..., s(k) in this order. This result will be used in [16].

U2 - 10.1017/S0963548307008759

DO - 10.1017/S0963548307008759

M3 - Article

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

SN - 1469-2163

VL - 17

JO - Combinatorics, Probability and Computing

JF - Combinatorics, Probability and Computing

IS - 03

ER -