The diameter of sparse random graphs

In this paper we study the diameter of the random graph $G(n,p)$, i.e., the the largest finite distance between two vertices, for a wide range of functions $p=p(n)$. For $p=\la/n$ with $\la>1$ constant, we give a simple proof of an essentially best possible result, with an $O_p(1)$ additive c...

ver descrição completa

Detalhes bibliográficos
Main Authors: Riordan, O, Wormald, N
Formato: Journal article
Idioma:English
Publicado em: 2008