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 vertices where each edge appears independently with probability p. For dense graphs, np→+∞, the tree-depth of a random graph G is aastd(...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2014-05, Vol.168, p.119-126
Main Authors: Perarnau, G., Serra, O.
Format: Article
Language:English
Subjects:
Asymptotic properties
Computation
Graphs
Linearity
Mathematical analysis
Mathematical models
Names
Proving
Random graphs
Tree-depth
Tree-width
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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→+∞, the tree-depth of a random graph G is aastd(G)=n−O(n/p). Random graphs with p=c/n, have aaslinear tree-depth when c>1, the tree-depth is Θ(logn) when c=1 and Θ(loglogn) for c1 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.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2012.10.031