Carregant...
Carregant...

Vés al contingut (premeu Retorn)

On the tree-depth of random graphs

Autor
Perarnau-Llobet, G.; Serra, O.
Tipus d'activitat
Article en revista
Revista
Discrete applied mathematics
Data de publicació
2014-05-11
Volum
168
Pàgina inicial
119
Pàgina final
126
DOI
https://doi.org/10.1016/j.dam.2012.10.031 Obrir en finestra nova
Projecte finançador
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 Obrir en finestra nova
Resum
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...
Paraules clau
ELIMINATION, Random graphs, TREEWIDTH, Tree-depth, Tree-width
Grup de recerca
COMBGRAPH - Combinatòria, Teoria de Grafs i Aplicacions
GAPCOMB - Geometric, Algebraic and Probabilistic Combinatorics

Participants