Longest cycles in sparse random digraphs

Details Longest cycles in sparse random digraphs Longest cycles in sparse random digraphs

2011-02-15

arxiv.org/abs/1102.3147v1

Mathematics

Combinatorics

14 pages

Scientific paper

Long paths and cycles in sparse random graphs and digraphs were studied intensively in the 1980's. It was finally shown by Frieze in 1986 that the random graph $\cG(n,p)$ with $p=c/n$ has a cycle on at all but at most $(1+\epsilon)ce^{-c}n$ vertices with high probability, where $\epsilon=\epsilon(c)\to 0$ as $c\to\infty$. This estimate on the number of uncovered vertices is essentially tight due to vertices of degree 1. However, for the random digraph $\cD(n,p)$ no tight result was known and the best estimate was a factor of $c/2$ away from the corresponding lower bound. In this work we close this gap and show that the random digraph $\cD(n,p)$ with $p=c/n$ has a cycle containing all but $(2+\epsilon)e^{-c}n$ vertices w.h.p., where $\epsilon=\epsilon(c)\to 0$ as $c\to\infty$. This is essentially tight since w.h.p. such a random digraph contains $(2e^{-c}-o(1))n$ vertices with zero in-degree or out-degree.

Affiliated with

Also associated with

No associations

Rating

Longest cycles in sparse random 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 Longest cycles in sparse random digraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Longest cycles in sparse random digraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-378846