Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

The diameter of random graphs


Author: Béla Bollobás
Journal: Trans. Amer. Math. Soc. 267 (1981), 41-52
MSC: Primary 05C99; Secondary 05C35, 60C05
MathSciNet review: 621971
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Extending some recent theorems of Klee and Larman, we prove rather sharp results about the diameter of a random graph. Among others we show that if $ d = d(n) \geqslant 3$ and $ m = m(n)$ satisfy $ (\log n)/d - 3\,\log \log n \to \infty $, $ {2^{d - 1}}{m^d}/{n^{d + 1}} - \log n \to \infty $ and $ {d^{d - 2}}{m^{d - 1}}/{n^d} - \log n \to - \infty $ then almost every graph with $ n$ labelled vertices and $ m$ edges has diameter $ d$.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C99, 05C35, 60C05

Retrieve articles in all journals with MSC: 05C99, 05C35, 60C05


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1981-0621971-7
PII: S 0002-9947(1981)0621971-7
Article copyright: © Copyright 1981 American Mathematical Society