Asymptotic approximation for the number of $n$-vertex graphs of given diameter

Asymptotic approximation for the number of $n$-vertex graphs of given diameter Full article

Journal

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Output data

Year: 2017, Volume: 11, Number: 2, Pages: 204-214 Pages count : 11 DOI: 10.1134/S1990478917020065

Tags

graph, labeled graph, shortest path, graph diameter, number of graphs, typical graph

Authors

Fedoryaeva T.I. ^1,2

Affiliations

1	Sobolev Institute of Mathematics
2	Novosibirsk State University

We prove that, for fixed k ≥ 3, 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.

Fedoryaeva T.I.
Asymptotic approximation for the number of $n$-vertex graphs of given diameter
Journal of Applied and Industrial Mathematics. 2017. V.11. N2. P.204-214. DOI: 10.1134/S1990478917020065 Scopus РИНЦ MathNet OpenAlex

Федоряева Т.И.
Асимптотическое приближение числа $n$-вершинных графов заданного диаметра
Дискретный анализ и исследование операций. 2017. Т.24. №2. 68-86 :1-19. DOI: 10.17377/daio.2017.24.534 РИНЦ MathNet

Submitted:	Mar 29, 2016
Published print:	May 25, 2017

Scopus:	2-s2.0-85019662822
Elibrary:	31036341
MathNet:	eng/da870
OpenAlex:	W2617490678

DB	Citing
Scopus	3
Elibrary	3
OpenAlex	1