6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could it be that the Laplacian analog does not require regularity? $\endgroup$ – Chris Godsil Nov 23 '15 at 12:33
  • $\begingroup$ @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. $\endgroup$ – David Roberson Nov 23 '15 at 13:02
  • $\begingroup$ @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). $\endgroup$ – Delio Mugnolo Nov 27 '15 at 9:19
  • 1
    $\begingroup$ @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. $\endgroup$ – David Roberson Nov 30 '15 at 14:27
1
$\begingroup$

Not sure if this helps, but you can get a somewhat similar result (in terms of the intersection numbers and arrays) from the bound (using your notation):

$$\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}$$

Perhaps your inequality follows from that one.

In the same paper they also show that $(\theta+1)(\tau+1)\leq-b_1$.

The original source of the first bound seems to be

  • A. Jurisic, Jack H. Koolen, P. Terwilliger, Tight distance-regular graphs. J. Algebraic Combin. 12(2) (2000)
$\endgroup$
  • $\begingroup$ I actually came across the same paper while looking around online. I couldn't see how to get my inequality out of theirs (the second one you mentioned actually) but I did not spend a lot of time on it. I should revisit it probably. Although, theirs only holds for distance regular graphs, not all regular graphs. $\endgroup$ – David Roberson Nov 26 '15 at 13:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.