Linkedness and ordered cycles in digraphs

Details Linkedness and ordered cycles in digraphs Linkedness and ordered cycles in digraphs

2007-04-02

arxiv.org/abs/0704.0211v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Linkedness and ordered cycles in digraphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linkedness and ordered cycles in digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linkedness and ordered cycles in digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-492393