Geodesic
Asymptotic approximation for the number of graphs
Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 68-86.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{DA_2017_24_2_a4,
     author = {T. I. Fedoryaeva},
     title = {Asymptotic approximation for the number of graphs},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {68--86},
     publisher = {mathdoc},
     volume = {24},
     number = {2},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2017_24_2_a4/}
}
TY  - JOUR
AU  - T. I. Fedoryaeva
TI  - Asymptotic approximation for the number of graphs
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2017
SP  - 68
EP  - 86
VL  - 24
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2017_24_2_a4/
LA  - ru
ID  - DA_2017_24_2_a4
ER  - 
%0 Journal Article
%A T. I. Fedoryaeva
%T Asymptotic approximation for the number of graphs
%J Diskretnyj analiz i issledovanie operacij
%D 2017
%P 68-86
%V 24
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2017_24_2_a4/
%G ru
%F DA_2017_24_2_a4
T. I. Fedoryaeva. Asymptotic approximation for the number of graphs. Diskretnyj analiz i issledovanie operacij, Tome 24 (2017) no. 2, pp. 68-86. http://geodesic.mathdoc.fr/item/DA_2017_24_2_a4/

[1] V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich, Lectures on Graph Theory, B. I. Wissenschaftsverlag, Mannheim, 1994 | MR | MR

[2] T. I. Fedoryaeva, “The diversity vector of balls of a typical graph of small diameter”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 43–54 (Russian) | DOI | MR | Zbl

[3] F. Harary, Graph Theory, Addison-Wesley, Reading, MA, USA, 1969 | MR | MR | Zbl

[4] S. V. Yablonskii, Introduction to Discrete Mathematics, Nauka, Moscow, 1986 (Russian) | MR

[5] Füredi Z., Kim Y., The number of graphs of given diameter, Cornell Univ. Libr. e-Print Archive, 2012, 13 pp., arXiv: 1204.4580[math.CO]

[6] Kim Y., Problems in extremal combinatorics, Thes. $\dots$ doct. philosophy (mathematics), Univ. Illinois Urbana-Champaign, Urbana, Champaign, 2011 | MR

[7] Moon J. W., Moser L., “Almost all $(0,1)$ matrices are primitive”, Stud. Sci. Math. Hung., 1 (1966), 153–156 | MR | Zbl

[8] Tomescu I., “An asymptotic formula for the number of graphs having small diameter”, Discrete Math., 156:1–3 (1996), 219–228 | DOI | MR | Zbl

[9] Tomescu I., “Almost all graphs and $h$-hypergraphs have small diameter”, Australas. J. Comb., 31 (2005), 313–323 | MR | Zbl