Том 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. |