2020/10/26 by А. А. Махнев, Makhnev, A. A.
Mathematics · Engineering · Computer Science · #Finite Group Theory Research #graph theory and CDMA systems #Coding theory and cryptography
paper · pdf · doi:10.48550/arxiv.2010.13443
If a regular graph of degree k and diameter d has v vertices then v≤ 1+k+k(k-1)+…+k(k-1)d-1. Graphs with v=1+k+k(k-1)+…+k(k-1)d-1 are called Moore graphs. Damerell proved that a Moore graph of degree k≥ 3 has diameter 2. If Γ is a Moore graph of diameter 2, then v=k2+1, Γ is strongly regular with λ=0 and μ=1, and one of the following statements holds\rm: k=2 and Γ is the pentagon, k=3 and Γ is the Petersen graph, k=7 and Γ is the Hoffman-Singleton graph, or k=57. The existence of a Moore graph of degree 57 was unknown. Jurishich and Vidali have proved that the existence of a Moore graph of degree k>3 is equivalent to the existence of a distance-regular graph with intersection array \k-2,k-3,2;1,1,k-3\ (in the case k=57 we have a distance-regular graph with intersection array \55,54,2;1,1,54\). In this paper we prove that a distance-regular graph with intersection array \55,54,2;1,1,54\ does not exist. As a corollary, we prove that a Moore graph of degree 57 does not exist.