Эта публикация цитируется в
8 статьях
О графах с заданными диаметром, числом вершин и локальным разнообразием шаров
Т. И. Федоряева Институт математики им. С. Л. Соболева СО РАН, г. Новосибирск, Россия
Аннотация:
В связи с задачей характеризации векторов разнообразия шаров обыкновенных связных графов изучаются
$n$-вершинные графы диаметра
$d$ с локальным
$t$-разнообразием шаров, т.е. графы, имеющие
$n$ различных шаров радиуса
$i$ для любого
$i\leq t$. Для таких графов справедлива нижняя оценка для числа вершин, определяемая через параметры
$d$ и
$t$. В статье с точностью до изоморфизма явно описываются все графы диаметра
$d$ с локальным
$t$-разнообразием шаров (полным разнообразием шаров), имеющие наименьший возможный порядок. Кроме того, для каждого такого графа вычисляется его вектор разнообразия шаров. Ил. 4, библиогр. 8.
Ключевые слова:
граф, диаметр графа, метрический шар, радиус шара, число шаров, вектор разнообразия шаров.
УДК:
519.17 Статья поступила: 16.06.2009
Переработанный вариант: 08.11.2009