A Spectral Moore Bound for Bipartite Semiregular Graphs

Abstract

Let $b(k,\ell ,\theta )$ be the maximum number of vertices of valency $k$ in a $(k,\ell )$-semiregular bipartite graph with second largest eigenvalue $\theta$. We obtain an upper bound for $b(k,\ell ,\theta )$ for $0<\theta <\sqrt{k-1}+\sqrt{\ell -1}$. This bound is tight when there exists a distance-biregular graph with particular parameters, and we develop the necessary properties of distance-biregular graphs to prove this.

25 pages

References in corpus (1)

• On the spectrum and linear programming bound for hypergraphs