The diameter of random graphs

Bollobás, Béla

doi:10.1090/S0002-9947-1981-0621971-7

The diameter of random graphs
HTML articles powered by AMS MathViewer

by Béla Bollobás

Trans. Amer. Math. Soc. 267 (1981), 41-52

DOI: https://doi.org/10.1090/S0002-9947-1981-0621971-7

PDF | Request permission

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

Béla Bollobás, Extremal graph theory, London Mathematical Society Monographs, vol. 11, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], London-New York, 1978. MR 506522
Béla Bollobás, Chromatic number, girth and maximal degree, Discrete Math. 24 (1978), no. 3, 311–314. MR 523321, DOI 10.1016/0012-365X(78)90102-4
Béla Bollobás, Graph theory, Graduate Texts in Mathematics, vol. 63, Springer-Verlag, New York-Berlin, 1979. An introductory course. MR 536131, DOI 10.1007/978-1-4612-9967-7
Béla Bollobás, Degree sequences of random graphs, Discrete Math. 33 (1981), no. 1, 1–19. MR 597223, DOI 10.1016/0012-365X(81)90253-3
B. Bollobás and P. Erdős, Cliques in random graphs, Math. Proc. Cambridge Philos. Soc. 80 (1976), no. 3, 419–427. MR 498256, DOI 10.1017/S0305004100053056
Kai Lai Chung, A course in probability theory, 2nd ed., Probability and Mathematical Statistics, Vol. 21, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1974. MR 0346858
P. Erdős, Graph theory and probability, Canadian J. Math. 11 (1959), 34–38. MR 102081, DOI 10.4153/CJM-1959-003-9
P. Erdős, Graph theory and probability. II, Canadian J. Math. 13 (1961), 346–352. MR 120168, DOI 10.4153/CJM-1961-029-9
P. Erdős and A. Rényi, On random graphs. I, Publ. Math. Debrecen 6 (1959), 290–297. MR 120167, DOI 10.5486/pmd.1959.6.3-4.12

On the evolution of random graphs

5

P. Erdős and Robin J. Wilson, On the chromatic index of almost all graphs, J. Combinatorial Theory Ser. B 23 (1977), no. 2-3, 255–257. MR 463022, DOI 10.1016/0003-4916(63)90266-5
William Feller, An introduction to probability theory and its applications. Vol. I, 3rd ed., John Wiley & Sons, Inc., New York-London-Sydney, 1968. MR 0228020
G. R. Grimmett and C. J. H. McDiarmid, On colouring random graphs, Math. Proc. Cambridge Philos. Soc. 77 (1975), 313–324. MR 369129, DOI 10.1017/S0305004100051124
Victor Klee and David Larman, Diameters of random graphs, Canadian J. Math. 33 (1981), no. 3, 618–640. MR 627647, DOI 10.4153/CJM-1981-050-1

On the diameter of graphs

12

Solution of a problem of Erdös and Rényi on Hamiltonian cycles in nonoriented graphs

17

David W. Matula, On the complete subgraphs of a random graph, Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970) Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 356–369. MR 0266796
J. W. Moon and L. Moser, Almost all $(0,\,1)$ matrices are primitive, Studia Sci. Math. Hungar. 1 (1966), 153–156. MR 209310

Hamiltonian cycles in random graphs

14