1683-3414 1814-0807 Владикавказский математический журнал Vladikavkaz Mathematical Journal Южный математический институт - филиал Федерального государственного бюджетного учреждения науки Федерального научного центра «Владикавказский научный центр Российской академии наук» (ЮМИ ВНЦ РАН) О кодах в дистанционно регулярных графах диаметра 3 On Codes in Distance-Regular Graphs of Diameter 3 10.46698/e5951-0245-2570-i 17182 09 2025 27 3 60 67 https://vmj.ru/archive/detail.php?ELEMENT_ID=17182&SECTION_ID=635 Журтов А. Х. Zhurtov A. Kh. zhurtov_a@mail.ru Гериева З. С. Gerieva Z. S. zuhra.geri17@gmail.com Кабардино-Балкарский госуниверситет, РОССИЯ, 360004, Нальчик, ул. Чернышевского, 175 Kabardino-Balkarian State University, 173 Chernyshevsky St., Nalchik 360004, Russia Пусть \(\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)\}\) также не существуют. Let \(\Gamma\) be a distance-regular graph of diameter \(d\). For \(i\in \{1,2,\ldots,d\}\) the graph \(\Gamma_i\) is defined on the vertex set of \(\Gamma\) and two vertices \(u\), \(w\) are adjacent in \(\Gamma_i\) if and only if (d_\Gamma(u,w)=i\). The Shilla graph is a distance-regular graph of diameter 3 with the eigenvalue \(\theta_1=a_3\). For the Shilla graph the number \(a=a_3\)\eject\noindent divides \(k\) and we set \(b=b(\Gamma)=k/a\). The Shilla graph has intersection array \(\{ab,(a+1)(b-1),b_2;c_1,c_2,a(b-1)\}\). Jurisic and Vidali found intersection arrays of distance-regular graphs of diameter 3 containing the maximal locally regular 1-code perfect with respect to the last neighborhood. Moreover, such graph \(\Gamma\) has intersection arrays \(\{a(p+1),cp,a+1;1,c,ap\}\) (and is a strongly regular graph \(\Gamma_3\)) or \(\{a(p+1),(a+1)p,c;1,c,ap\}\) (and is a Shilla graph). In this manuscript we study graphs \(\Gamma\) such that it contains the maximal locally regular 1-code. For a distance-regular graph with intersection array \(\{a^2,a^2-1,c;1,c,a(a-1)\}\) and \(a<1000\), \(c<1000\), the multiplicities of the eigenvalues are integer only in the cases \((a,c)=(3,4)\) (and \(q^1_{13}<0\)), \((a,c)=(5,3)\), \((a,c)=(9,18)\) (and \(q^3_{33}<0\)), \((a,c)=(21,49)\) (and \(q^3_{33}<0\)), \((a,c)=(21,9)\). Thus, only arrays \(\{25,24,3;1,3,20\}\) and \(\{441,440,9;1,9,420\}\) remain. Moreover, a distance-regular graph with intersection array \(\{a^2,a^2-1,c;1,c,a(a-1)\}\) does not exist. As a consequence, distance-regular graphs with intersection arrays \(\{25,24,3;1,3,20\}\) and \(\{(441,440,9;1,9,420)\}\) do not exist. дистанционно регулярный граф сильно регулярный граф граф Шилла distance-regular graph strongly regular graph Shilla graph 1 Koolen J., Park J. Shilla distance-regular graphs // Europ. J. Comb. 2010. Vol. 31, № 8. P. 2064-2073. DOI: 10.1016/j.ejc.2010.05.012. Koolen, J. and Park, J. Shilla Distance-Regular Graphs, European Journal of Combinatorics, 2010, Vol. 31, no. 8. pp. 2064-2073. DOI: 10.1016/j.ejc.2010.05.012. 2 Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. Berlin-Heidelberg-New York: Springer-Verlag, 1989. 495 p. DOI: 10.1007/978-3-642-74341-2. Brouwer, A. E., Cohen, A. M. and Neumaier, A. Distance-Regular Graphs, Berlin, Heidelberg, New York, Springer-Verlag, 1989, 495 p. DOI: 10.1007/978-3-642-74341-2. 3 Jurishich A., Vidali J. Extremal 1-codes in distance-regular graphs of diameter 3 // Des. Codes Cryptogr. 2012. Vol. 65. P. 29-47. Jurishich, A. and Vidali, J. Extremal 1-Codes in distance-Regular Graphs of Diameter 3, Designs, Codes and Cryptography, 2012, vol. 65, pp. 29-47. 4 Нирова М. С. О дистанционно регулярных графах \(\Gamma\) с сильно регулярными графами \(\Gamma_2\) и \(\Gamma_3\) // Сиб. электрон. матем. изв. 2018. Т. 15. C. 175-185. DOI: 10.17377/semi.2018.15.017. Nirova, M. S. On Distance-Regular Graphs \(\Gamma\) with Strongly Regular Graphs \(\Gamma_2\) and \(\Gamma_3\), Siberian Electronic Mathematical Reports, 2018, vol. 15, pp. 175-185. DOI: 10.17377/semi.2018.15.017. 5 Белоусов И. Н. Дистанционно регулярные графы Шилла с \(b_2=sc_2\) // Тр. Ин-та математики и механики УрО РАН. 2018. Т. 24, № 3. C. 16-26. DOI: 10.21538/0134-4889-2018-24-3-16-26. Belousov, I. N. Distance-Regular Graphs \(\Gamma\) with \(b_2=sc_2\), Proceedings of the Steklov Institute of Mathematics (Supplement Issues), 2019, vol. 307, no. 1, pp. S23-S33. DOI: 10.1134/S0081543819070034. 6 Махневa А. А., Нирова М. С. Дистанционно регулярные графы Шилла с \(b_2=c_2\) // Матем. заметки. 2018. Т. 103, № 5. C. 730-744. DOI: 10.4213/mzm11503. Makhnev, A. A. and Nirova, M. S. On Distance-Regular Shilla Graphs, Mathematical Notes, 2018, vol. 103, no. 5, pp. 780-792. DOI: 10.1134/S0001434618050103. 7 Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory, Ser. A. 2008. Vol. 115. P. 1086-1095.DOI: 10.1016/j.jcta.2007.12.001. Coolsaet, K. and Jurishich, A. Using Equality in the Krein Conditions to Prove Nonexistence of Certain Distance-Regular Graphs, Journal of Combinatorial Theory, Series A, 2008, vol. 115, no. 6, pp. 1086-1095.DOI: 10.1016/j.jcta.2007.12.001.