Том 17, номер 1, 2010 г., Стр. 65–74

УДК 519.17
Федоряева Т. И.
О графах с заданными диаметром, числом вершин и локальным разнообразием шаров

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

Ключевые слова: граф, диаметр графа, метрический шар, радиус шара, число шаров, вектор разнообразия шаров.

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

Статья поступила 16 июня 2009 г.
Исправленный вариант — 8 ноября 2009 г.