Abstract: 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.

Cite: 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 WOS Scopus РИНЦ OpenAlex

Dates:

Submitted:	Dec 6, 2023
Published online:	Dec 31, 2024
Published print:	May 15, 2025

Identifiers:

Web of science:	WOS:001422789500001
Scopus:	2-s2.0-85213532163
Elibrary:	80831750
OpenAlex:	W4405963208

Citing: Пока нет цитирований

Altmetrics: