A spectral version of the Moore problem for bipartite regular graphs

Source abstract

Let b ( k , θ ) be the maximum order of a connected bipartite k -regular graph whose second largest eigenvalue is at most θ . In this paper, we obtain a general upper bound for b ( k , θ ) for any 0 ≤ θ < 2 k - 1 . Our bound gives the exact value of b ( k , θ ) whenever there exists a bipartite distance-regular graph of degree k , second largest eigenvalue θ , diameter d and girth g such that g ≥ 2 d - 2 . For certain values of d , there are infinitely many such graphs of various valencies k . However, for d = 11 or d ≥ 15 , we prove that there are no bipartite distance-regular graphs with g ≥ 2 d - 2 .