Q-полиномиальный граф с массивом пересечений {60, 45, 8; 1, 12, 50} не существует
DOI:
https://doi.org/10.17072/1993-0550-2023-2-29-33Ключевые слова:
блок-схема, дистанционно регулярный граф, Q-полиномиальный графАннотация
При исследовании вполне регулярных графов Γ диаметра d, в которых для некоторой вершины a пара (Γd(a), Γd-1(a)) является 2-схемой, доказано, что подграф, индуцированный множеством точек, является кликой, кокликой или сильно регулярным графом. Для графа диаметра 3 установлено, что указанная конструкция является 2-схемой для любой вершины a тогда и только тогда, когда граф дистанционно регулярен и для любой вершины a подграф Γ3(a) является кликой, кокликой или сильно регулярным графом (А.Л. Гаврилюк, А.А. Махнев). Интересным представляется вопрос о существовании дистанционно регулярного графа с массивом пересечений {60,45,8;1,12,50}, для которого Γ3(a) может быть 6×6-решеткой и пара (Γ3(a), Γ2(a)) будет 2-схемой. В работе И.Н. Белоусова и А.А. Махнева (2018) опубликовано доказательство несуществования вышеуказанного графа, содержащее ошибки. В данной работе приводится корректное доказательство этого результата.Библиографические ссылки
Гаврилюк А.Л., Махнев А.А. Вполне регулярные графы и блок-схемы // Сиб. матем. жур-нал. 2006. Т. 47, № 4. С. 753–768.
Gavrilyuk A.L. Makhnev A.A. Automorphisms of graphs with intersection arrays {60, 45, 8; 1, 12, 50} and {49, 36, 8; 1, 6, 42} // Mathematical Zametki. 2017. Vol. 101, № 6. 823–831.
Белоусов И.Н., Махнев А.А. Дистанционно регулярные графы с массивами пересечений {42, 30, 12; 1, 6, 28} и {60, 45, 8; 1, 12, 50} не существуют // Сибирские электрон. матем. известия. 2018. Т. 15. 1506–1512.
Coolsaet K., Juriˇsi´c A. Using equality in the Krein conditions to prove nonexistence of certain distance-regular graphs // J. Comb. Theory, Series A. 2008. Vol. 115. 1086–1095.
Brouwer A.E., Cohen A.N., Neumaier A. Distance-Regular Graphs // Springer-Verlag. Berlin Heidelberg New-York, 1989.
Gavrilyuk A., Koolen J. A characterization of the graphs of bilinear dxd-forms over F2 // Combinatorica. 2019. Vol. 39, № 2. 289–321.
Загрузки
Опубликован
Как цитировать
Выпуск
Раздел
Лицензия
Copyright (c) 2023 Александр Алексеевич Махнев, Виктория Васильевна Биткина, Алина Казбековна Гутнова
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Публикация статьи в журнале осуществляется на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0).
