Linkedness and Ordered Cycles in Digraphs

Research output: Contribution to journalArticle

Colleges, School and Institutes

Abstract

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].

Details

Original languageEnglish
JournalCombinatorics, Probability and Computing
Volume17
Issue number03
Early online date28 Sep 2007
Publication statusPublished - 1 May 2008