Том 14, серия 1, номер 2, 2007 г., Стр. 47-67

УДК 519.17
Т. И. Федоряева
Векторы разнообразия шаров для графов и оценки их компонент

Аннотация:
Изучаются векторы разнообразия шаров ($i$-я компонента векторa равна числу различных шаров радиуса $i$) для обыкновенных связных графов и свойства их компонент. Получены точные верхние и нижние оценки числа различных шаров заданного радиуса для $n$-вершинных графов (деревьев) и $n$-вершинных деревьев (графов при $n\geqslant 2d$) диаметра $d$. Показана достижимость таких оценок в одном графе независимо от рассматриваемого радиуса шаров. Доказано необходимое и достаточное условие существования $n$-вершинного графа диаметра $d$ с локальным (полным) разнообразием шаров.
Библ. 8.

Федоряева Т. И. ¹
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: sfdd@academ.org

Статья поступила 30 июня 2006 г.
Исправленный вариант — 28 марта 2007 г.