Loading...
Loading...

Go to the content (press return)

On the tree-depth of random graphs

Author
Perarnau-Llobet, G.; Serra, O.
Type of activity
Journal article
Journal
Discrete applied mathematics
Date of publication
2014-05-11
Volume
168
First page
119
Last page
126
DOI
https://doi.org/10.1016/j.dam.2012.10.031 Open in new window
Project funding
Optimización y problemas extremales en teoria de grafos y combinatoria. Aplicacions a les redes de comunicación
URL
http://www.sciencedirect.com/science/article/pii/S0166218X12004118 Open in new window
Abstract
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...
Keywords
ELIMINATION, Random graphs, TREEWIDTH, Tree-depth, Tree-width
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants