Graphs with three eigenvalues from group divisible designs

Abstract

We construct biregular graphs with three distinct eigenvalues from semiregular group divisible designs. For every prime power $q$, we use the spectral structure of Muzychuk's Construction~A on $q+1$ copies of $\mathrm{AG}(2,q^2)$ to produce suitable group divisible designs. The resulting biregular graphs have $2q^5+q^4+q^2$ vertices and distinct eigenvalues $q^5+q^3+q^2$, $q^2$, and $-q^2$. Their coherent closures have rank $12$ and type $\left[\begin{array}{cc}3& 2\\ 2& 5\end{array}\right]$. We also determine the four-class symmetric association schemes that are the coherent closures of the auxiliary graphs in this family. Computational searches provide further graphs on $81$ and $156$ vertices, using Muzychuk's Construction~B and a generalised quadrangle, respectively; their coherent closures have ranks $13$ and $10$. The $156$-vertex example has a strongly regular design as its coherent closure, of type $\left[\begin{array}{cc}3& 2\\ 2& 3\end{array}\right]$, answering a question of the authors. We also realise a $126$-vertex example by switching a strongly regular graph.

arXiv comment28 pages