Asymptotic approximation for the number of $n$-vertex graphs of given diameter | Sciact - Система учета научной деятельности ИМ СО РАН

Asymptotic approximation for the number of $n$-vertex graphs of given diameter Научная публикация

Журнал

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

Вых. Данные

Год: 2017, Том: 11, Номер: 2, Страницы: 204-214 Страниц : 11 DOI: 10.1134/S1990478917020065

Ключевые слова

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

Авторы

Fedoryaeva T.I. ^1,2

Организации

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

Поступила в редакцию:	29 мар. 2016 г.
Опубликована в печати:	25 мая 2017 г.

Scopus:	2-s2.0-85019662822
РИНЦ:	31036341
MathNet:	eng/da870
OpenAlex:	W2617490678

БД	Цитирований
Scopus	4
РИНЦ	3
OpenAlex	1