О кодах в дистанционно регулярных графах диаметра $3$

А. Х. Журтов, З. С. Гериева

Кабардино-Балкарский государственный университет им. Х. М. Бербекова, Россия, 360004, Нальчик, ул. Чернышевского, 173

Аннотация: Пусть $\Gamma$ является дистанционно регулярным графом диаметра $d$. Для $i\in \{1,2,\ldots,d\}$ граф $\Gamma_i$ определен на множестве вершин графа $\Gamma$ и две вершины $u$, $w$ смежны в $\Gamma_i$ тогда и только тогда, когда $d_\Gamma(u,w)=i$. Графом Шилла называется дистанционно регулярный граф диаметра $3$ с собственным значением $\theta_1=a_3$. Для графа Шилла число $a=a_3$ делит $k$ и полагают $b=b(\Gamma)=k/a$. Граф Шилла имеет массив пересечений $\{ab,(a+1)(b-1),b_2;c_1,c_2,a(b-1)\}$. А. Юришич и Я. Видали нашли массивы пересечений дистанционно регулярных графов диаметра $3$, содержащих максимальный локально регулярный $1$-код, совершенный относительно последней окрестности. Оказалось, что такой граф $\Gamma$ имеет массив пересечений $\{a(p+1),cp,a+1;1,c,ap\}$ (и сильно регулярный граф $\Gamma_3$) или $\{a(p+1),(a+1)p,c;1,c,ap\}$ (и является графом Шилла). В работе изучаются графы $\Gamma$, содержащие максимальный локально регулярный $1$-код. Для дистанционно регулярного графа c массивом пересечений $\{a^2,a^2-1,c;1,c,a(a-1)\}$ и $a<1000$, $c<1000$ кратности собственных значений целые только в случаях $(a,c)=(3,4)$ (и $q^1_{13}<0$), $(a,c)=(5,3)$, $(a,c)=(9,18)$ (и $q^3_{33}<0$), $(a,c)=(21,49)$ (и $q^3_{33}<0$), $(a,c)=(21,9)$. Таким образом, остались только массивы $\{25,24,3;1,3,20\}$ и $\{441,440,9;1,9,420)\}$. При этом дистанционно регулярный граф c массивом пересечений $\{a^2,a^2-1,c;1,c,a(a-1)\}$ не существует. Как следствие, дистанционно регулярные графы c массивами пересечений $\{25,24,3;1,3,20\}$ и $\{441,440,9;1,9,420)\}$ также не существуют.

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

УДК: 519.17

MSC: 05E30, 05C50

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

DOI: 10.46698/e5951-0245-2570-i