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: | , |
---|---|
Format: | Journal article |
Language: | English |
Published: |
2008
|