On the tree-depth of Random Graphs

Details On the tree-depth of Random Graphs On the tree-depth of Random Graphs

2011-04-12

arxiv.org/abs/1104.2132v2

Mathematics

Combinatorics

13 pages

Scientific paper

The tree-depth is a parameter introduced under several names as a measure of sparsity of a graph. We compute asymptotic values of the tree-depth of random graphs. For dense graphs, p>> 1/n, the tree-depth of a random graph G is a.a.s. td(G)=n-O(sqrt(n/p)). Random graphs with p=c/n, have a.a.s. linear tree-depth when c>1, the tree-depth is Theta (log n) when c=1 and Theta (loglog n) for c<1. The result for c>1 is derived from the computation of tree-width and provides a more direct proof of a conjecture by Gao on the linearity of tree-width recently proved by Lee, Lee and Oum. We also show that, for c=1, every width parameter is a.a.s. constant, and that random regular graphs have linear tree-depth.

Affiliated with

Also associated with

No associations

Rating

On the tree-depth of Random Graphs 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 On the tree-depth of Random Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the tree-depth of Random Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-730975