RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2006, том 47, номер 4, страницы 753–768 (Mi smj892)

Эта публикация цитируется в 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


 Англоязычная версия: Siberian Mathematical Journal, 2006, 47:4, 621–633

Реферативные базы данных:


© МИАН, 2024