Асимптотическое приближение числа $n$-вершинных графов заданного диаметра

Асимптотическое приближение числа $n$-вершинных графов заданного диаметра Full article

Journal

Дискретный анализ и исследование операций
ISSN: 1560-7542

Output data

Year: 2017, Volume: 24, Number: 2, Article number : 68-86, Pages count : 19 DOI: 10.17377/daio.2017.24.534

Tags

граф, помеченный граф, кратчайшая цепь, диаметр графа, число графов, типичный граф

Authors

Fedoryaeva Tatiana Ivanovna ^1,2

Affiliations

1	Институт математики им. С.Л. Соболева СО РАН
2	Новосибирский государственный университет

Доказано, что при фиксированном k≥3 асимптотически равномощны следующие классы помеченных n-вершинных графов: графы диаметра k, связные графы диаметра не менее k и графы (не обязательно связные), имеющие кратчайшую цепь длины не менее k. Получено асимптотически точное приближение числа таких n-вершинных графов, и найдена явная оценка погрешности при этом приближении. Тем самым улучшены оценки для асимптотического приближения числа n-вершинных графов фиксированного диаметра k, которое ранее получили Фюреди и Ким. Установлено, что почти все графы диаметра k имеют единственную пару диаметральных вершин, но почти все графы диаметра 2 имеют более одной пары таких вершин.

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

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

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

Elibrary:	29275515
MathNet:	rus/da870

Пока нет цитирований