Том 20, номер 1, 2013 г., Стр. 58-76
УДК 519.1+519.173+519.176
Федоряева Т. И.
Мажоранты и миноранты класса графов с фиксированными диаметром и числом вершин
Аннотация:
Изучаются мажоранты (миноранты) класса n-вершинных графов диаметра d, т. е. экстремальные графы, на которых достигаются точные верхние (нижние) оценки числа различных шаров радиуса i для любого i ≥ 0. Явно описываются миноранты при всех значениях параметров n и d. Устанавливается, когда в классе n-вершинных графов диаметра d существуют мажоранты, и описываются такие экстремальные графы.
Ил. 9, библиогр. 8.
Ключевые слова: граф, метрический шар, радиус шара, число шаров, оценки числа шаров, экстремальный граф.
Федоряева Татьяна Ивановна 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: tatiana.fedoryaeva@gmail.com
Статья поступила 23 марта 2012 г.
Исправленный вариант — 17 мая 2012 г.
Литература
[1] Евдокимов А. А. Локально изометрические вложения графов и свойство продолжения метрики // Сиб. журн. исслед. операций. - 1994. - Т. 1, № 1. - С. 5–12.
[2] Федоряева Т. И. О разнообразии метрических шаров в графах // Проблемы теоретической кибернетики. Тез. докл. XIV Междунар. конф. (Пенза, 23–28 мая 2005 г.). - М.: Изд-во мех.-мат. фак-та МГУ, 2005. - С. 159.
[3] Федоряева Т. И. Разнообразие шаров в метрических пространствах деревьев // Дискрет. анализ и исслед. операций. Сер. 1. - 2005. - Т. 12, № 3. - C. 74–84.
[4] Федоряева Т. И. Векторы разнообразия шаров и свойства их компонент // Тр. VII Междунар. конф. «Дискретные модели в теории управляющих систем» (Москва, 4–6 марта 2006 г.). - М.: Изд-во МГУ, 2006. - С. 374–378.
[5] Федоряева Т. И. Векторы разнообразия шаров для графов и оценки их компонент // Дискрет. анализ и исслед. операций. Сер. 1. - 2007. - Т. 14, № 2. - C. 47–67.
[6] Федоряева Т. И. Точные верхние оценки числа различных шаров заданного радиуса в графах с фиксированными числом вершин и диаметром // Дискрет. анализ и исслед. операций. - 2009. - Т. 16, № 6. - C. 74–92.
[7] Федоряева Т. И. О графах с заданными диаметром, числом вершин и локальным разнообразием шаров // Дискрет. анализ и исслед. операций. - 2010. - Т. 17, № 1. - C. 65–74.
[8] Харари Ф. Теория графов. - М.: Мир, 1973. - 300 c.
