1683-34141814-0807Владикавказский математический журналVladikavkaz Mathematical JournalЮжный математический институт - филиал Федерального государственного бюджетного учреждения науки Федерального научного центра «Владикавказский научный центр Российской академии наук» (ЮМИ ВНЦ РАН)О двудольных \(Q\)-полиномиальных графах диаметра, не большего 5On Bipartite \(Q\)-Polynomial Graphs of Diameter Not Greater than \(5\)10.46698/y5679-0662-9249-a171710920252732127https://vmj.ru/archive/detail.php?ELEMENT_ID=17171&SECTION_ID=635БиткинаВ. В.BitkinaV. V.bviktoriyav@mail.ruМахневА. А.MakhnevA. A.makhnev@imm.uran.ruСеверо-Осетинский государственный университет им. К. Л. Хетагурова, РОССИЯ, 362025, Владикавказ, ул. Ватутина, 44-46North Ossetian State University, 44--46 Vatutin St., Vladikavkaz 362025, RussiaХайнаньский университет, КИТАЙ, 570228, Хэйкоу, Хайнань, пр. Ренмин, 58Hainan Provincial University, 58 Renmin Ave., Haikou 570228, Hainan, ChinaПусть \(u\) - вершина двудольного \(Q\)-полиномиального дистанционно регулярного графа \(\Gamma\) диаметра \(D\ge 3\), \(\Sigma=\Gamma_D(u)\) и \(\Lambda=\Sigma_2\). Тогда \(\Lambda\) - дистанционно регулярный \(Q\)-полиномиальный граф. В случаях \(D=4\) и \(D=5\) граф \(\Lambda\) является сильно регулярным \(Q\)-полиномиальным. Половинный граф \(\Gamma_2\) сильно регулярен и \(\Lambda\) - окрестность вершины в дополнении к \(\Gamma_2\). Поэтому необходимое условие \(Q\)-полиномиальности \(\Gamma\) - это сильная регулярность окрестностей и антиокрестностей вершин в \(\Lambda\).
Двудольный дистанционно регулярный граф \(\Gamma\) диаметра \(D\in \{4,5\}\) назовем почти \(Q\)-полиномиальным, если окрестности и антиокрестности вершин в дополнении его половинного графа сильно регулярны. Имеется два допустимых массива пересечений \(Q\)-полиномиальных графов: \(\{10,9,8,7,6;1,2,3,4,10\}\) (свернутый 10-куб) и \(\{55,54,50,35,10;1,5,20,45,55\}\). Эти графы имеют сильно регулярные графы \(\Lambda\) (параметры \((126,25,8,4)\) и \((210,99,48,45)\)) и окрестности вершин в \(\Lambda\) (параметры \((25,8,4,2)\) и \((99,48,22,24)\)). Имеются два допустимых массива пересечений, отвечающих графам на \(704\) вершинах: \(\{26,25,24,2,1;1,2,24,25,26\}\) и \(\{36,34,32,4,1;1,4,32,34,36\}\). В работе изучаются почти \mbox{\(Q\)-полиномиальные} графы диаметра \(5\). Доказано, что дистанционно регулярные графы с массивами пересечений \(\{26,25,24,2,1;1,2,24,25,26\}\) и \(\{36,35,32,4,1;1,4,32,35,36\}\) не существуют.Let \(u\) be a vertex of a bipartite \(Q\)-polynomial distance-regular graph \(\Gamma\) of diameter \(D\ge 3\), \(\Sigma=\Gamma_D(u)\), and \(\Lambda=\Sigma_2\). Then \(\Lambda\) is a distance-regular \(Q\)-polynomial graph. In the cases \(D=4\) and \(D=5\) the graph \(\Lambda\) is strongly regular \(Q\)-polynomial. The half graph \(\Gamma_2\) is strongly regular and \(\Lambda\) is a neighbourhood of a vertex in the complement of \(\Gamma_2\). Therefore, a necessary condition for \(Q\)-polynomiality of \(\Gamma\) is the strong regularity of neighbourhoods and antineighbourhoods of vertices in \(\Lambda\). A bipartite distance-regular graph \(\Gamma\) of diameter \(D\in \{4,5\}\) is called almost \(Q\)-polynomial if neighbourhoods and antineighbourhoods of vertices in its half-graph are strongly regular. There are two admissible intersection arrays of \(Q\)-polynomial graphs: \(\{10,9,8,7,6;1,2,3,4,10\}\) (a folded 10-cube) and \(\{55,54,50,35,10;1,5,20,45,55\}\). These graphs have strongly regular graphs \(\Lambda\) (parameters \((126,25,8,4)\) and \((210,99,48,45)\)) and neighbourhoods of vertices in \(\Lambda\) (parameters \((25,8,4,2)\) and \((99,48,22,24)\)). There are two admissible intersection arrays corresponding to graphs on \(704\) vertices: \(\{26,25,24,2,1;1,2,24,25,26\}\) and \(\{36,34,32,4,1;1,4,32,34,36\}\). In this manuscript we study almost \(Q\)-polynomial graphs of diameter \(5\). We obtain that distance-regular graphs with intersection arrays \(\{26,25,24,2,1;1,2,24,25,26\}\) and \(\{36,35,32,4,1;1,4,32,35,36\}\) do not exist.дистанционно регулярный граф\(Q\)-полиномиальный графдвудольный графdistance-regular graph\(Q\)-polynomial graphbipartite graphBrouwer A. E., Cohen A. M., Neumaier A. Distance-Regular Graphs. New York: Springer-Verlag, 1989. 495 p. DOI: 10.1007/978-3-642-74341-2.Coolsaet K., Jurishich A. Using equality in the Krein conditions to prove nonexistence of сertain distance-regular graphs // J. Comb. Theory, Series A. 2008. Vol. 115, № 6. P. 1086-1095. DOI: 10.1016/j.jcta.2007.12.001.Vidali J. Using symbolic computation to prove nonexistence of distance-regular graphs //Electron. Journal of Comb. 2018. Vol. 25, № 4. Article № P4.21. DOI: 10.37236/7763.