Loading...
Loading...

Go to the content (press return)

On the tree depth of random graphs

Author
Perarnau-Llobet, G.; Serra, O.
Type of activity
Presentation of work at congresses
Name of edition
VII Jornadas de Matemática Discreta y Algorítmica
Date of publication
2010
Presentation's date
2010-06-15
Book of congress proceedings
VII Jornadas Matemática Discreta y Algorítmica : libro de actas
First page
517
Last page
529
Repository
http://hdl.handle.net/2117/11262 Open in new window
URL
http://www.jmda2010.unican.es/Librodeactas.pdf Open in new window
Abstract
The tree-depth of a graph G is a parameter that plays a crucial role in the theory of bounded expansion classes and has been introduced under numerous names. We describe the asymptotic behaviour of this parameter in the case of dense and of sparse random graphs. The results also provide analogous descriptions for the tree-width of random graphs.
Citation
Perarnau-Llobet, G.; Serra, O. On the tree depth of random graphs. A: VII Jornadas de Matemática Discreta y Algorítmica. "VII Jornadas de Matemática Discreta y Algorítmica". Castro Urdiales: 2010, p. 517-529.
Group of research
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants