|
Teoriya Veroyatnostei i ee Primeneniya, 1974, Volume 19, Issue 4, Pages 740–754
(Mi tvp3977)
|
|
|
|
This article is cited in 8 scientific papers (total in 8 papers)
On extreme metric parameters of a random graph, I
Yu. D. Burtin Leningrad
Abstract:
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<t<\infty$, 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)$.
Received: 01.03.1973
Citation:
Yu. D. Burtin, “On extreme metric parameters of a random graph, I”, Teor. Veroyatnost. i Primenen., 19:4 (1974), 740–754; Theory Probab. Appl., 19:4 (1975), 710–725
Linking options:
https://www.mathnet.ru/eng/tvp3977 https://www.mathnet.ru/eng/tvp/v19/i4/p740
|
|