Том 22, номер 6, 2015 г., Стр. 43–54
УДК 519.1+519.173
Федоряева Т. И.
Вектор разнообразия шаров типичного графа малого диаметра
Аннотация:
Изучаются векторы разнообразия шаров (i-я компонента вектора равна числу различных шаров радиуса i) для обыкновенных связных графов в асимптотике. Для графов малого диаметра исследовано асимптотическое поведение числа графов с полным разнообразием шаров. Вычислен вектор разнообразия шаров типичного графа заданного малого диаметра. Найдено асимптотически точное значение числа помеченных n-вершинных графов диаметра 3.
Ил. 2, библиогр. 12.
Ключевые слова: граф, метрический шар, радиус шара, число ша- ров, вектор разнообразия шаров, типичный граф.
DOI: 10.17377/daio.2015.22.512
Федоряева Татьяна Ивановна 1,2
1. Институт математики им. С. Л. Соболева,
пр. Коптюга, 4, 630090 Новосибирск, Россия
2. Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: tatiana.fedoryaeva@gmail.com
Статья поступила 20 сентября 2015 г.
Исправленный вариант — 26 октября 2015 г.
Литература
[1] Евдокимов А. А. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. 1994. Т. 1, № 1. С. 5–12.
[2] Евдокимов А. А. Об одном подходе к классификации графов как метрических пространств // Тезисы докл. XI Междунар. конф. по пробл. теорет. кибернетики (Ульяновск, 10–14 июня 1996 г.). M.: Изд-во МГУ, 1996. С. 57–59.
[3] Евдокимов А. А., Федоряева Т. И. О проблеме характеризации векторов разнообразия шаров // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 1. С. 44–52.
[4] Федоряева Т. И. Операции и изометрические вложения графов, связанные со свойством продолжения метрики // Дискрет. анализ и исслед. операций. 1995. Т. 2, № 3. C. 49–67.
[5] Федоряева Т. И. Разнообразие шаров в метрических пространствах деревьев // Дискрет. анализ и исслед. операций. Сер. 1. 2005. Т. 12, № 3. C. 74–84.
[6] Федоряева Т. И. Векторы разнообразия шаров для графов и оценки их компонент // Дискрет. анализ и исслед. операций. Сер. 1. 2007. Т. 14, № 2. C. 47–67.
[7] Федоряева Т. И. Точные верхние оценки числа различных шаров заданного радиуса в графах с фиксированными числом вершин и диаметром // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 6. C. 74–92.
[8] Федоряева Т. И. О графах с заданными диаметром, числом вершин и локальным разнообразием шаров // Дискрет. анализ и исслед. операций. 2010. Т. 17, № 1. C. 65–74.
[9] Федоряева Т. И. Мажоранты и миноранты класса графов с фиксированными диаметром и числом вершин // Дискрет. анализ и исслед. операций. 2013. Т. 20, № 1. C. 58–76.
[10] Харари Ф. Теория графов. М.: Мир, 1973. 300 с.
[11] Bollobás B. Graph theory: an indroductory course. New York: Springer-Verl., 1979. 394 p.
[12] Tomescu I. An asymptotic formula for the number of graphs having small diameter // Discrete Math. 1996. Vol. 156, No. 1–3. P. 219–228. (Grad. Texts Math.; Vol. 63).
