RUS  ENG
Полная версия
ЖУРНАЛЫ // Труды Института математики и механики УрО РАН // Архив

Тр. ИММ УрО РАН, 2016, том 22, номер 3, страницы 50–61 (Mi timm1321)

Эта публикация цитируется в 2 статьях

О графах Деза с несвязной второй окрестностью вершины

С. В. Горяиновab, Г. С. Исаковаa, В. В. Кабановb, Н. В. Масловаbc, Л. В. Шалагиновa

a Челябинский государственный университет
b Институт математики и механики им. Н. Н. Красовского Уральского отделения РАН, г. Екатеринбург
c Уральский федеральный университет им. первого Президента России Б. Н. Ельцина, г. Екатеринбург

Аннотация: Граф $\Gamma$ называется графом Деза, если $\Gamma$ регулярен и число общих соседей пары произвольных различных вершин принимает одно из двух значений. Точным графом Деза называется граф Деза диаметра $2$, не являющийся сильно регулярным графом. В 1992 г. Гарднер (Gardiner), Годсил (Godsil), Хенсел (Hensel) и Ройл (Royle) показали, что сильно регулярный граф, содержащий вершину с несвязной второй окрестностью, является полным многодольным графом с долями одинакового размера, больше либо равного $2$. В данной работе мы изучаем точные графы Деза с несвязной второй окрестностью вершин. В разд. $2$ мы докажем, что если каждая вершина точного графа Деза имеет несвязную вторую окрестность, то этот граф является либо реберно регулярным, либо кореберно регулярным. В разд. $3$ и $4$ мы изучаем точный граф Деза, содержащий по крайней мере одну вершину с несвязной второй окрестностью. В разд. $3$ показано, что если такой граф реберно регулярен, то он является $s$-кокликовым расширением сильно регулярного графа с параметрами $(n,k,\lambda, \mu)$, где $s \ge 2$ и $\lambda = \mu$. В разд. $4$ показано, что если такой граф кореберно регулярен, то он является $2$-кликовым расширением полного многодольного графа с долями одинакового размера, больше либо равного $3$.

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

УДК: 519.17

MSC: 05C40, 05C07

Поступила в редакцию: 10.12.2015

DOI: 10.21538/0134-4889-2016-22-3-50-61


 Англоязычная версия: Proceedings of the Steklov Institute of Mathematics (Supplementary issues), 2017, 297, suppl. 1, 97–107

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


© МИАН, 2024