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...
Main Authors: | , |
---|---|
Formato: | Journal article |
Idioma: | English |
Publicado em: |
2008
|