1683-34141814-0807Владикавказский математический журналVladikavkaz Mathematical JournalЮжный математический институт - филиал Федерального государственного бюджетного учреждения науки Федерального научного центра «Владикавказский научный центр Российской академии наук» (ЮМИ ВНЦ РАН)Примитивные сильно регулярные графы без треугольников с \(\mu=3\) не существуютPrimitive Strongly Regular Triangle-Free Graphs with \(\mu=3\) do not Exist10.46698/b1924-8658-8779-p198580920262834450https://vmj.ru/archive/detail.php?ELEMENT_ID=19858&SECTION_ID=673БелоусоваВ. И.BelousovaV. I.vkazarina@mail.ruЛиХайянLeeH.lhy9694@163.comМахневА. А.MakhnevA. A.makhnev@imm.uran.ruУральский федеральный университет, РОССИЯ, 620002, Екатеринбург, ул. Мира, 19Ural Federal University, 19 Mira St., Ekaterinburg 620002, RussiaХайнаньский университет, ИТАЙ, 57228, провинция Хайнань, Хайкоу, пр. Жэньминь Дадао, 58Hainan Provincial University, 58 Renmin Dadao Ave., Hainan Province, Haikou 570228, ChinaЕсли \(\Gamma\) - антиподальный дистанционно регулярный граф диаметра 4 с сильно регулярным графом \(\Gamma_{1,2}\), то \(\Gamma_{3,4}\) - сильно регулярный граф без треугольников. Для графа \(\Gamma\) с массивом пересечений \(\{20,18,3,1;1,3,18,20\}\) граф \(\Gamma_{3,4}\) имеет параметры \((162,21,0,3)\). Графы небольших степеней имеют массивы пересечений \(\{20,18,3,1;1,3,18,20\}\), \(\{25,24,2,1;1,2,24,25\}\) и \(\{32,27,6,1;1,6,27,32\}\), \(\{36,25,2,1;1,2,25,36\}\). Граф с массивом пересечений \(\{32,27,6,1;1,6,27,32\}\) не существует. Любой сильно регулярный граф \(\Gamma\) без треугольников с \(\mu=3\) имеет параметры \((162,21,0,3)\). Такой граф существует тогда и только тогда, когда определено его двудольное удвоение (дистанционно регулярный граф с массивом пересечений \(\{21,20,9,3,1;1,3,9,20,21\}\)). В работе доказано, что сильно регулярный граф с параметрами \((162,21,0,3)\) не существует. Как следствие, дистанционно регулярный граф с~массивом пересечений \(\{20,18,3,1;1,3,18,20\}\) и двудольный дистанционно регулярный граф с~массивом пересечений \(\{36,35,47,6;1,9,30,36\}\) не существуют.If \(\Gamma\) is an antipodal distance-regular graph of diameter 4 with strongly regular graph \(\Gamma_{1,2}\), then \(\Gamma_{3,4}\) is a strongly regular graph without triangles. For a graph \(\Gamma\) with intersection array \(\{20,18,3,1;1,3,18,20\}\), the graph \(\Gamma_{3,4}\) has parameters (162,21,0,3). Graphs of small degrees have intersection arrays \(\{20,18,3,1;1,3,18,20\}\), \(\{25,24,2,1;1,2,24,25\}\) and \(\{32,27,6,1;1,6,27,32\}\), \(\{36,25,2,1;1,2,25,36\}\). A graph with array \(\{32,27,6,1;1,6,27,32\}\) does not exist. Any strongly regular triangle-free graph \(\Gamma\) with \(\mu=3\) has parameters (162,21,0,3). A strongly regular graph with parameters \((162,21,0,3)\) is defined if and only if its bipartite doubling (a distance-regular graph with intersection array \(\{21,20,9,3,1;1,3,9,20,21\}\)) is defined. It is proved in the paper that a strongly regular graph with parameters \((162,21,0,3)\) does not exist. As a consequence, a distance-regular graph with intersection array \(\{20,18,3,1;1,3,18,20\}\) and a bipartite distance-regular graph with intersection array \(\{36,35,47,6;1,9,30,36\}\)
do not exist.дистанционно регулярный графсильно регулярный графантиподальный графdistance-regular graphstrongly regular graphantipodal graphИсследование выполнено при поддержке Естественно-научного фонда Китая (проект 12171126) и гранта Лаборатории инженерного моделирования и статистических вычислений провинции Хайнань.Brouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. Berlin-Heidelberg-New York: Springer-Verlag, 1989. 495 p.<div> 1. Brouwer, A. E., Cohen, A. M. and Neumaier, A. Distance-Regular Graphs, Berlin, Heidelberg, New York, Springer-Verlag, 1989, 495 p.</div>Dalf'o C., Fiol M., Koolen J. The spectral excess theorem for graphs with few eigenvalues whose distance-2 or distance-1-or-2 graph is strongly regular // Linear and Multilinear Algebra. 2018. Vol. 67, № 12. P. 2373-2381. DOI: 10.1080/03081087.2018.1491944.Dalfó, C., Fiol, M. and Koolen, J. The Spectral Excess Theorem for Graphs with Few Eigenvalues Whose Distance-2 or Distance-1-or-2 Graph is Strongly Regular, Linear and Multilinear Algebra, 2018, vol. 67, no. 12, pp. 2373-2381. DOI: 10.1080/03081087.2018.1491944.Махнев А. А., Падучих Д. В. Обратные задачи в классе дистанционно регулярных графов диаметра 4 // Тр. Института математики и механики УрО РАН. 2022. Т. 28, № 1. С. 199-208. DOI: 10.21538/0134-4889-2022-28-1-199-208.Makhnev, A. and Paduchikh, D. Inverse Problems in Distance-Regular Graphs of Diameter 4, Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 1, pp. 199-208 (in Russian). DOI: 10.21538/0134-4889-2022-28-1-199-208.Makhnev A., Paduchikh D. Small AT4-graphs and strongly regular subgraphs corresponding to them // Proceedings of the Steklov Institute of Mathematics. 2017. Vol. 296, № 1. P. 164-174. DOI: 10.1134/S0081543817020158.Makhnev, A. and Paduchikh, D. Small AT4-Graphs and Strongly Regular Subgraphs Corresponding to Them, Proceedings of the Steklov Institute of Mathematics, 2017, vol. 296, no. 1, pp. 164-174. DOI: 10.1134/S0081543817020158.Soicher L. The uniqueness of a distance-regular graph with intersection array {32,27,8,1;1,4,27,32} and related results // Designs, Codes and Cryptography. 2017. Vol. 84, № 1-2. P. 101-108. DOI: 10.1007/s10623-016-0223-6.Soicher, L. The Uniqueness of a Distance-Regular Graph with Intersection Array {32,27,8,1;1,4,27,32} and Related Results, Designs, Codes and Cryptography, 2017, vol. 84, no. 1-2, pp. 101-108. DOI: 10.1007/s10623-016-0223-6.Coolsaet K., Jurišić A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory, Series A. 2008. Vol. 115, № 6. P. 1086-1095. DOI: 10.1016/j.jcta.2007.12.001.Coolsaet, K. and Jurišić, 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.