EN|RU

Англоязычная версия:
Journal of Applied and Industrial Mathematics, 2017, 11:2, 204-214

Том 24, номер 2, 2017 г., Стр. 68-86

УДК 519.1+519.175
Федоряева Т. И.
Асимптотическое приближение числа $n$-вершинных графов заданного диаметра

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

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

DOI: 10.17377/daio.2017.24.534

Федоряева Татьяна Ивановна 1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: tatiana.fedoryaeva@gmail.com

Статья поступила 29 марта 2016 г.
Исправленный вариант — 4 июля 2016 г.

Литература

[1] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.

[2] Федоряева Т. И. Вектор разнообразия шаров типичного графа малого диаметра // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 6. C. 43–54.

[3] Харари Ф. Теория графов. М.: Мир, 1973. 300 с.

[4] Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.

[5] Füredi Z., Kim Y. The number of graphs of given diameter // arXiv:1204.4580v [math.CO]. 2012. P. 13.

[6] Kim Y. Problems in extremal combinatorics: Thes. . . . doct. philosophy (mathematics). Univ. Illinois — Urbana-Champaign, 2011.

[7] Moon J. W., Moser L. Almost all (0,1) matrices are primitive // Stud. Sci. Math. Hung. 1966. Vol. 1. P. 153–156.

[8] Tomescu I. An asymptotic formula for the number of graphs having small diameter // Discrete Math. 1996. Vol. 156, No. 1–3. P. 219–228.

[9] Tomescu I. Almost all graphs and h-hypergraphs have small diameter // Australas. J. Comb. 2005. Vol. 31. P. 313–323.

 © Институт математики им. С. Л. Соболева, 2015