Journal article icon

Journal article

The diameter of sparse random graphs

Abstract:

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 correction term. Using similar techniques, we establish 2-point concentration in the case that $np\to\infty$. For $p=(1+\epsilon)/n$ with $\epsilon\to 0$, we obtain a corresponding result that applies a...

Expand abstract
Publication status:
Published

Actions


Access Document


Publisher copy:
10.1017/S0963548310000325
Journal:
Combinatorics, Probability and Computing 19 (2010), 835--926 More from this journal
Volume:
19
Issue:
5-6
Pages:
835-926
Publication date:
2008-08-29
DOI:
EISSN:
1469-2163
ISSN:
0963-5483
Language:
English
Keywords:
Pubs id:
pubs:107111
UUID:
uuid:cfcb5fa5-7242-4071-99f3-b07863a699cd
Local pid:
pubs:107111
Source identifiers:
107111
Deposit date:
2012-12-19

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP