On extreme metric parameters of a~random graph,~I

Yu. D. Burtin

Teoriâ veroâtnostej i ee primeneniâ, Tome 19 (1974) no. 4, pp. 740-754

Résumé

A random graph $G_n(t)$ is considered such that the edge between every pair of its vertices exists with the probability $p=1-e^{-t}$, $0$, independently from the other edges. Let $L=[\log_{nt}n]$ be the integer part of $\log_{nt}n$. Then, uniformly in $t\ge(c_n \log n)/n$ $(\lim_{n\to\infty}c_n=\infty)$, $$ \lim_{n\to\infty}\mathbf P(L+l\le d(G_n(t))\le L+2)=1, $$ where $d(G_n(t))$ denotes the diameter of the random graph. Thus the limit distribution of the diameter may be concentrated at at most two points. Analogous propositions hold true for the radius and the cycle index of the random graph $G_n(t)$.