A characterization of Johnson and Hamming graphs and proof of Babai's conjecture

Abstract

One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with $\mu \ge 2$ and second largest eigenvalue ${\theta }_1=b_1-1$. In this paper we give a classification under the (weaker) approximate eigenvalue constraint ${\theta }_1\ge (1-\epsilon )b_1$ for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs.

34 pages

References in corpus (1)

• On the spectral gap and the automorphism group of distance-regular graphs

Cited by in corpus (1)

• Hamming sandwiches