|
Title:
|
On the tree depth of random graphs
|
|
Author:
|
Perarnau Llobet, Guillem; Serra Albó, Oriol
|
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada IV |
|
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. |
|
Publication date:
|
2012-05-11 |
|
Subject(s):
|
Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs
Random graphs
Graph theory
Mathematical models
Grafs, Teoria de
Models matemàtics |
|
Rights:
|
Restricted access - publisher's policy |
|
Document type:
|
Conference Object |
|
Share:
|
|
