DIKUL - logo
E-resources
Peer reviewed Open access
  • A characterization of Johns...
    Kivva, Bohdan

    Journal of combinatorial theory. Series B, November 2021, 2021-11-00, Volume: 151
    Journal Article

    •In this paper, we characterize Hamming and Johnson graphs by their spectral gap.•We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter.•Our characterization of Hamming graphs involves only inequality constraints. One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ≥2 and second largest eigenvalue θ1=b1−1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ1≥(1−ε)b1 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 of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut(X) has minimal degree ≥cn for some constant c>0. It follows that Aut(X) satisfies strong structural constraints.