On the automorphism group of a distance-regular graph

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\ge 3$ on $n$ vertices is at least $Cn/(\log n{)}^6$ 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.

16 pages