|
Teoriya Veroyatnostei i ee Primeneniya, 1975, Volume 20, Issue 1, Pages 82–98
(Mi tvp2991)
|
|
|
|
This article is cited in 7 scientific papers (total in 7 papers)
On extreme metric characteristics of a random graph. II. Limit distributions
Yu. D. Burtin Leningrad
Abstract:
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.
Received: 01.03.1973
Citation:
Yu. D. Burtin, “On extreme metric characteristics of a random graph. II. Limit distributions”, Teor. Veroyatnost. i Primenen., 20:1 (1975), 82–98; Theory Probab. Appl., 20:1 (1975), 83–101
Linking options:
https://www.mathnet.ru/eng/tvp2991 https://www.mathnet.ru/eng/tvp/v20/i1/p82
|
|