Эта публикация цитируется в
4 статьях
Вполне регулярные графы и блок-схемы
А. Л. Гаврилюк,
А. А. Махнев Институт математики и механики УрО РАН
Аннотация:
Исследуются вполне регулярные графы
$\Gamma$ диаметра
$d$, в которых для некоторой вершины
$a$ множество вершин, находящихся на расстоянии
$d$ от
$a$, является множеством точек 2-схемы, множество блоков которой состоит из пересечений окрестностей точек с множеством вершин, находящихся на расстоянии
$d-1$ от
$a$. Доказано, что подграф, индуцированный множеством точек, является кликой, кокликой или сильно регулярным графом диаметра 2. Для графа диаметра 3 установлено, что указанная конструкция является 2-схемой для любой вершины
$a$ тогда и только тогда, когда граф дистанционно регулярен и для любой вершины
$a$ подграф
$\Gamma_3(a)$ является кликой, кокликой или сильно регулярным графом. Получен список возможных параметров для схем и графов диаметра 3 при условии, что подграф, индуцированный множеством точек, является графом Зейделя. Показано, что некоторые из найденных параметров не могут отвечать дистанционно регулярным графам.
Ключевые слова:
вполне регулярный граф, $t-(v,k,\lambda)$-схема, сильно регулярный граф.
УДК:
519.14 Статья поступила: 12.05.2004
Окончательный вариант: 30.12.2005