Граф $\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$.
Переведенное названиеOn Deza graphs with disconnected second neighborhood of a vertex
Язык оригиналаРусский
Страницы (с-по)50-61
Число страниц12
ЖурналТруды института математики и механики УрО РАН
Том22
Номер выпуска3
DOI
СостояниеОпубликовано - 2016

    Уровень публикации

  • Перечень ВАК

ID: 1285205