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 vertices where each edge appears independently with probability p. For dense graphs, np -> +infinity, the tree-depth of a random graph G is aas td(G) = n - O ( root n/p). Random graphs with p = c/n, have aaslinear tree-depth when c > 1, the tree-depth is (-)(log n) when c = 1 and (-) (log log n) for c < 1. The result for c > 1 is deri...
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 vertices where each edge appears independently with probability p. For dense graphs, np -> +infinity, the tree-depth of a random graph G is aas td(G) = n - O ( root n/p). Random graphs with p = c/n, have aaslinear tree-depth when c > 1, the tree-depth is (-)(log n) when c = 1 and (-) (log log 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 (2012) [15]. We also show that, for c = 1, every width parameter is aasconstant, and that random regular graphs have linear tree-depth. (c) 2012 Elsevier B.V. All rights reserved.