Дистанционно регулярные графы с массивами пересечений {7,6,6;1,1,2} и {42,30,2;1,10,36} не существуют

Махнев А. А. , Биткина В. В. , Гутнова А. К.
Владикавказский математический журнал. 2021. Том 23. Выпуск 4.С.68-76.

Аннотация:
Пусть \(\Gamma\) - дистанционно регулярный граф диаметра 3 без треугольников, \(u\) - вершина графа \(\Gamma\), \(\Delta^i=\Gamma_i(u)\) и \(\Sigma^i=\Delta^i_{2,3}\). Тогда \(\Sigma^i\) - регулярный граф без 3-коклик степени \(k'=k_i-a_i-1\) на \(v'=k_i\) вершинах. Заметим, что для несмежных вершин \(y,z\in \Sigma^i\) имеем \(\Sigma^i=\{y,z\}\cup \Sigma^i(y)\cup \Sigma^i(z)\). Поэтому для \(\mu'=|\Sigma^i(y)\cap \Sigma^i(z)|\) имеем равенство \(v'=2k'+2-\mu'\). Отсюда граф \(\Sigma\) является кореберно регулярным с параметрами \((v',k',\mu')\). В работе доказано, что дистанционно регулярный граф с массивом пересечений \(\{7,6,6;1,1,2\}\) не существует. В статье М. С. Нировой "On distance-regular graphs with \(\theta_2=-1\)" показано, что если существует сильно регулярный граф с параметрами \((176,49,12,14)\), в котором окрестности вершин являются \(7\times 7\)-решетками, то существует и дистанционно регулярный граф с массивом пересечений \(\{7,6,6;1,1,2\}\). М.~П. Голубятников заметил, что для дистанционно регулярного графа \(\Gamma\) с массивом пересечений \(\{7,6,6;1,1,2\}\) граф \(\Gamma_2\) является дистанционно регулярным с массивом пересечений \(\{42,30,2;1,10,36\}\). С помощью этого результата и вычисления тройных чисел пересечений доказано, что дистанционно регулярные графы с массивами пересечений \(\{7,6,6;1,1,2\}\) и \(\{42,30,2;1,10,36\}\) не существуют.

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

Язык статьи: Русский Загрузить полный текст  

+ Список литературы