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).
