Q-полиномиальный граф с массивом пересечений {60, 45, 8; 1, 12, 50} не существует
Автор: Махнев А.А., Биткина В.В., Гутнова А.К.
Журнал: Вестник Пермского университета. Серия: Математика. Механика. Информатика @vestnik-psu-mmi
Рубрика: Математика
Статья в выпуске: 2 (61), 2023 года.
Бесплатный доступ
При исследовании вполне регулярных графов Γ диаметра 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) опубликовано доказательство несуществования вышеуказанного графа, содержащее ошибки. В данной работе приводится корректное доказательство этого результата.
Блок-схема, дистанционно регулярный граф, q-полиномиальный граф
Короткий адрес: https://sciup.org/147245546
IDR: 147245546 | DOI: 10.17072/1993-0550-2023-2-29-33
Список литературы Q-полиномиальный граф с массивом пересечений {60, 45, 8; 1, 12, 50} не существует
- Гаврилюк А.Л., Махнев А.А. Вполне регулярные графы и блок-схемы // Сиб. матем. журнал. 2006. Т. 47, № 4. С. 753-768. EDN: KXEXNB
- 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. EDN: LQZUXQ
