# Eigenvalue inequality for regular graphs

I recently proved an inequality relating some of the eigenvalues of a regular graph with each other, and I was wondering if it is already known. I was unable to find it online, and a quick skim through Spectra Of Graphs by Brouwer and Haemers did not locate it. The inequality is as follows:

Let $G$ be a connected $k$-regular graph on $n$ vertices which is not complete. Let $\theta$ be the second largest eigenvalue of (the adjacency matrix of) $G$, and let $\tau$ be its minimum eigenvalue. Then, $$\theta \ge \frac{k(n+\tau-k)}{\tau - n\tau - k}$$ with equality if and only if $G$ is strongly regular.

I came upon the inequality in a very roundabout way, but then found a quite simple proof, so I thought it may already be known. It is probably not a very useful inequality since it only relates eigenvalues to each other and not to any other parameters of the graph. Perhaps this is why it is hard to find online if it is indeed already known.

• Could it be that the Laplacian analog does not require regularity? Nov 23, 2015 at 12:33
• @ChrisGodsil Not sure. Seems like the Laplacian analog of the eigenvalue $k$ is 0, so the righthand side would just be zero, in which case the inequality would hold for any graph since the Laplacian is positive semidefinite. Hopefully the above inequality is not quite so trivial. Maybe I am getting the analog wrong though. I don't know a whole lot about the Laplacian (don't let my PhD advisor know). Perhaps I should just post the proof of the inequality and then someone may see what the Laplacian analog should be. Nov 23, 2015 at 13:02
• @DavidE.Roberson Yes, I would be very interested in the proof. Characterising a subclass of graphs by spectral means is often a very relevant step, in particular if you could also prove some kind of monotonicity (the "less strongly regular" a graph is, the larger the gap in your inequality). Nov 27, 2015 at 9:19
• @DelioMugnolo Let $A$ and $\overline{A}$ be the adjacency matrix of the graph and its complement. Then $A - \tau I$ and $\overline{A} - (-\theta -1)I - \frac{n-k+\theta}{n}J$ are PSD. We then have $$0 \le Tr\left((A - \tau I)(\overline{A} - (-\theta -1)I - \frac{n-k+\theta}{n}J)\right)$$ which is equal to the sum of the entrywise product of the two matrices. Arithmetic reveals the bound. We have equality in the bound iff the trace is 0 which happens iff the column spaces of the two matrices are orthogonal iff $k$, $\theta$, and $\tau$ are the only eigenvalues of $A$ iff G is SRG. Nov 30, 2015 at 14:27

$$\left(\theta + \frac{k}{a_1+1}\right)\left(\tau+\frac{k}{a_1+1}\right)\geq \frac{ka_1b_1}{(a_1+1)^2}$$
In the same paper they also show that $(\theta+1)(\tau+1)\leq-b_1$.