Teoriya Veroyatnostei i ee Primeneniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Teor. Veroyatnost. i Primenen.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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
Full-text PDF (923 kB) Citations (7)
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
English version:
Theory of Probability and its Applications, 1975, Volume 20, Issue 1, Pages 83–101
DOI: https://doi.org/10.1137/1120007
Bibliographic databases:
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Bur75}
\by Yu.~D.~Burtin
\paper On extreme metric characteristics of a~random graph. II.~Limit distributions
\jour Teor. Veroyatnost. i Primenen.
\yr 1975
\vol 20
\issue 1
\pages 82--98
\mathnet{http://mi.mathnet.ru/tvp2991}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=369169}
\zmath{https://zbmath.org/?q=an:0351.60013}
\transl
\jour Theory Probab. Appl.
\yr 1975
\vol 20
\issue 1
\pages 83--101
\crossref{https://doi.org/10.1137/1120007}
Linking options:
  • https://www.mathnet.ru/eng/tvp2991
  • https://www.mathnet.ru/eng/tvp/v20/i1/p82
  • This publication is cited in the following 7 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Теория вероятностей и ее применения Theory of Probability and its Applications
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024