О ГРАФАХ ДЕЗА С НЕСВЯЗНОЙ ВТОРОЙ ОКРЕСТНОСТЬЮ ВЕРШИНЫ

Сергей Викторович Горяинов, Галина Сергеевна Исакова, Владислав Владимирович Кабанов, Наталья Владимировна Маслова, Леонид Викторович Шалагинов

Resultado de la investigación: Articlerevisión exhaustiva

Resumen

Граф $\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$.
Título traducido de la contribuciónOn Deza graphs with disconnected second neighborhood of a vertex
Idioma originalRussian
Páginas (desde-hasta)50-61
Número de páginas12
PublicaciónТруды института математики и механики УрО РАН
Volumen22
N.º3
DOI
EstadoPublished - 2016

Level of Research Output

  • VAK List

Citar esto