On the automorphism group of a distance-regular graph

2023/12/01 by László Pyber, Saveliy V. Skresanov, Pyber, László +1
Mathematics · Engineering · #Finite Group Theory Research #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2312.00383

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/(log n)⁶ for some universal constant C > 0, unless it is a Johnson, a Hamming or a crown graph. This follows using an improvement of an earlier result by Kivva who gave a lower bound on motion of the form n/c_d, where c_d depends exponentially on d. As a corollary we derive a quasipolynomial upper bound for 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.

Related

• Automorphism group of a family of distance regular graphs which are not distance transitive
• On the automorphism groups of distance-regular graphs and rank-4\n primitive coherent configurations
• On some distance-regular graphs with many vertices
• The least Euclidean distortion constant of a distance-regular graph
• Locally s-distance transitive graphs