What is the smallest and the largest possible adjacency eigenvalue of a regular graph?

Question

For a $d$-regular graph I think $d$ is always the largest adjacency eigenvalue and if its bipartite then I think $-d$ is the smallest possible.

Answer 1

If you consider a vector of all $1$s, then the matrix will map it to a vector of all $d$s. So $d$ can be attained as an eigenvalue. This is maximal by the Gerschgorin circle theorem, which tells you (among other things) that an eigenvalue $\lambda_i$ must be in a closed disk in the complex plane centered at $a_{ii}$ with radius $\displaystyle \sum_{j=1,j \neq i}^n |a_{ij}|$. For the adjacency matrix of a $d$-regular graph, $a_{ii} = 0$ and the radius is $d$.

In the bipartite case, if you consider a vector which is $1$ on one part and $-1$ on the other, then the adjacency matrix will switch the locations of the minus signs and then scale everything by $d$ again. So this will give you an eigenvalue of $-d$. Again the Gerschgorin circle theorem tells you this is the minimal possibility for any $d$-regular graph. Of course in the non-bipartite case the smallest eigenvalue is probably larger.