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

Журтов А. Х.  , Гериева З. С.
Владикавказский математический журнал. 2025. Том 27. Выпуск 3.С.60-67.

Аннотация:
Пусть \(\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)\}\) также не существуют.

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

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

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