On extreme metric characteristics of a~random graph. II.~Limit distributions

Yu. D. Burtin

Teoriâ veroâtnostej i ee primeneniâ, Tome 20 (1975) no. 1, pp. 82-98

Résumé

The paper continues the investigation of asymptotic statistical properties of the metric structure of the random graph $G_n(t)$ that has been started in the previous paper of the author. The random graph $G_n(t)$ may be constructed by independent elimination of edges from the complete non-oriented graph with $n$ verticies, every edge being removed with the probability $e^{-t}$. The paper contains limit theorems for a number of metric characteristics of the random graph concerned with the diameter, the radius, the cycle index and with the conceptions of independent and dominating sets. Let, e.g., $L=[\log_{nt}n]$ denote the integer part of $\log_{nt}n$. If $\lim\limits_{n\to\infty}(nt/\log^3n)=\infty$, $(nt)^{L+1/n}=2\log n+x+o(1)$, $x=\text{const}$, then $$ \lim_{n\to\infty}\mathbf P(d(G_n(t))=L+1)=1-\lim\limits_{n\to\infty}\mathbf P(d(G_n(t))=L+2)=\exp\biggl(-\frac12e^{-x}\biggr), $$ where $d(G_n(t))$ is the diameter of the random graph.