|
Сибирский математический журнал, 2006, том 47, номер 4, страницы 753–768
(Mi smj892)
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 5 статьях)
Вполне регулярные графы и блок-схемы
А. Л. Гаврилюк, А. А. Махнев Институт математики и механики УрО РАН
Аннотация:
Исследуются вполне регулярные графы $\Gamma$ диаметра $d$, в которых для некоторой вершины $a$ множество вершин, находящихся на расстоянии $d$ от $a$, является множеством точек 2-схемы, множество блоков которой состоит из пересечений окрестностей точек с множеством вершин, находящихся на расстоянии $d-1$ от $a$. Доказано, что подграф, индуцированный множеством точек, является кликой, кокликой или сильно регулярным графом диаметра 2. Для графа диаметра 3 установлено, что указанная конструкция является 2-схемой для любой вершины $a$ тогда и только тогда, когда граф дистанционно регулярен и для любой вершины $a$ подграф $\Gamma_3(a)$ является кликой, кокликой или сильно регулярным графом. Получен список возможных параметров для схем и графов диаметра 3 при условии, что подграф, индуцированный множеством точек, является графом Зейделя. Показано, что некоторые из найденных параметров не могут отвечать дистанционно регулярным графам.
Ключевые слова:
вполне регулярный граф, $t-(v,k,\lambda)$-схема, сильно регулярный граф.
Статья поступила: 12.05.2004 Окончательный вариант: 30.12.2005
Образец цитирования:
А. Л. Гаврилюк, А. А. Махнев, “Вполне регулярные графы и блок-схемы”, Сиб. матем. журн., 47:4 (2006), 753–768; Siberian Math. J., 47:4 (2006), 621–633
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/smj892 https://www.mathnet.ru/rus/smj/v47/i4/p753
|
Статистика просмотров: |
Страница аннотации: | 468 | PDF полного текста: | 133 | Список литературы: | 60 |
|