On the automorphism group of a distance-regular graph Научная публикация
Журнал |
Journal of Combinatorial Theory. Series B
ISSN: 0095-8956 , E-ISSN: 1096-0902 |
||||
---|---|---|---|---|---|
Вых. Данные | Год: 2025, Том: 172, Страницы: 94-114 Страниц : 21 DOI: 10.1016/j.jctb.2024.12.005 | ||||
Ключевые слова | Distance-regular graph, Automorphism group, Motion, Diameter | ||||
Авторы |
|
||||
Организации |
|
Информация о финансировании (1)
1 | Институт математики им. С.Л. Соболева СО РАН | FWNF-2022-0002 |
Реферат:
The motion of a graph is the minimal degree of its full automorphism group. Babai conjectured that the motion of a primitive distance-regular graph on n vertices of diameter greater than two is at least n/C for some universal constant C>0, unless the graph is a Johnson or Hamming graph. We prove that the motion of a distance-regular graph of diameter d ≥ 3 on n vertices is at least Cn/(logn)6 for some universal constant C>0, unless it is a Johnson, Hamming or crown graph. To show this, we improve an earlier result by Kivva who gave a lower bound on motion of the form n/cd, where cd depends exponentially on d. As a corollary we derive a quasipolynomial upper bound for the size of the automorphism group of a primitive distance-regular graph acting edge-transitively on the graph and on its distance-2 graph. The proofs use elementary combinatorial arguments and do not depend on the classification of finite simple groups. © 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Библиографическая ссылка:
Pyber L.
, Skresanov S.V.
On the automorphism group of a distance-regular graph
Journal of Combinatorial Theory. Series B. 2025. V.172. P.94-114. DOI: 10.1016/j.jctb.2024.12.005 Scopus OpenAlex
On the automorphism group of a distance-regular graph
Journal of Combinatorial Theory. Series B. 2025. V.172. P.94-114. DOI: 10.1016/j.jctb.2024.12.005 Scopus OpenAlex
Даты:
Поступила в редакцию: | 6 дек. 2023 г. |
Опубликована online: | 31 дек. 2024 г. |
Опубликована в печати: | 15 мая 2025 г. |
Идентификаторы БД:
Scopus: | 2-s2.0-85213532163 |
OpenAlex: | W4405963208 |
Цитирование в БД:
Пока нет цитирований