Асимптотическое приближение числа $n$-вершинных графов заданного диаметра | Sciact - Система учета научной деятельности ИМ СО РАН

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

Журнал

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

Вых. Данные

Год: 2017, Том: 24, Номер: 2, Номер статьи : 68-86, Страниц : 19 DOI: 10.17377/daio.2017.24.534

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

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

Авторы

Федоряева Татьяна Ивановна ^1,2

Организации

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

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

РИНЦ:	29275515
MathNet:	rus/da870

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