Linkedness and Ordered Cycles in Digraphs

Research output: Contribution to journalArticle

3 Citations (Scopus)

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].
Original languageEnglish
JournalCombinatorics, Probability and Computing
Volume17
Issue number03
Early online date28 Sep 2007
DOIs
Publication statusPublished - 1 May 2008

Fingerprint

Dive into the research topics of 'Linkedness and Ordered Cycles in Digraphs'. Together they form a unique fingerprint.

Cite this