RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretn. Anal. Issled. Oper., 2017, Volume 24, Number 2, Pages 68–86 (Mi da870)  

Asymptotic approximation for the number of graphs

T. I. Fedoryaevaab

a Sobolev Institute of Mathematics, 4 Acad. Koptyug Ave., 630090 Novosibirsk, Russia
b Novosibirsk State University, 2 Pirogov St., 630090 Novosibirsk, Russia

Abstract: We prove that, for fixed $k\geq3$, the following classes of labeled $n$-vertex graphs are asymptotically equicardinal: graphs of diameter $k$, connected graphs of diameter at least $k$, and (not necessarily connected) graphs with a shortest path of length at least $k$. An asymptotically exact approximation of the number of such $n$-vertex graphs is obtained, and an explicit error estimate in the approximation is found. Thus, the estimates are improved for the asymptotic approximation of the number of $n$-vertex graphs of fixed diameter $k$ earlier obtained by Füredi and Kim. It is shown that almost all graphs of diameter $k$ have a unique pair of diametrical vertices but almost all graphs of diameter 2 have more than one pair of such vertices. Illustr. 3, bibliogr. 9.

Keywords: graph, labeled graph, shortest path, graph diameter, number of graphs, ordinary graph.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-01-00949
Russian Academy of Sciences - Federal Agency for Scientific Organizations 0314-2015-0011


DOI: https://doi.org/10.17377/daio.2017.24.534

Full text: PDF file (363 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 204–214

UDC: 519.1+519.175
Received: 29.03.2016
Revised: 04.07.2016

Citation: T. I. Fedoryaeva, “Asymptotic approximation for the number of graphs”, Diskretn. Anal. Issled. Oper., 24:2 (2017), 68–86; J. Appl. Industr. Math., 11:2 (2017), 204–214

Citation in format AMSBIB
\Bibitem{Fed17}
\by T.~I.~Fedoryaeva
\paper Asymptotic approximation for the number of graphs
\jour Diskretn. Anal. Issled. Oper.
\yr 2017
\vol 24
\issue 2
\pages 68--86
\mathnet{http://mi.mathnet.ru/da870}
\crossref{https://doi.org/10.17377/daio.2017.24.534}
\elib{http://elibrary.ru/item.asp?id=29275515}
\transl
\jour J. Appl. Industr. Math.
\yr 2017
\vol 11
\issue 2
\pages 204--214
\crossref{https://doi.org/10.1134/S1990478917020065}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85019662822}


Linking options:
  • http://mi.mathnet.ru/eng/da870
  • http://mi.mathnet.ru/eng/da/v24/i2/p68

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Дискретный анализ и исследование операций
    Number of views:
    This page:194
    Full text:17
    References:18
    First page:14

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020