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