On the tree-depth of random graphs ?
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 a random graph on n n vertices where each edge appears independently with probability p p . For dense graphs, np?+? n p ? + ? , the tree-depth of a random graph G G is aas  td ( G ) = n ? O ( n / p ) . Random graphs with p=c/n p = c / n , have aas linear tree-depth when c>1 c > 1 , the tree-depth is ?(logn) ? ( log n ) when c=1 c = 1 and ?(loglogn) ? ( log log n ) for c 1 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 (2012) [15]. We also show that, for c=1 c = 1 , every width parameter is aasconstant, and that random regular graphs have linear tree-depth.
tree-depth random graphs tree-width