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/