The sum of the two largest eigenvalues (Solved)

Importance: Medium ✭✭
Author(s): Gernert, Dieter
Keywords: eigenvalues
Recomm. for undergrads: no
Posted by: mdevos
on: June 6th, 2007
Solved by: Vladimir Nikiforov, Linear Combinations of Graph Eigenvalues, Electronic Journal of Linear Algebra 15 pp 329-336

\begin{problem} Let $G$ be a graph on $n$ vertices and let $\lambda_1 \ge \lambda_2 \ge \ldots \ge \lambda_n$ be the eigenvalues of $G$. Is $\lambda_1 + \lambda_2 \le n$? \end{problem}

This property does hold for all regular graphs $G$. If $G$ is $k$-regular, then $\lambda_1 = k$. Further, if we let $\bar{G}$ denote the complement of $G$ and let $\bar{\lambda_1} \ge \bar{\lambda_2}, \ldots \ge \bar{\lambda_n}$ denote its eigenvalues, then $\lambda_2 = -1 - \bar{\lambda_n} \le -1 + (n-k-1)$ (the second inequality here follows from the observation that $\bar{G}$ is $(n-k-1)$-regular).


\href[Open Problems in Spectral Graph Theory]{} (a list maintained by Dragan Stevanović).

* indicates original appearance(s) of problem.


About 5 months ago, I was shown a counterexample to this conjecture by Bojan Mohar (I believe in joint work with two of his grad. students - Javad Ebrahimi and Azhvan Sheikh). However, thanks to Gordon Royle, I have just learned that this problem was resolved earlier by Vladimir Nikiforov. See \href[Linear combinations of graph eigenvalues]{}.

Is this really solved?

I'm confused how the paper's result (which you have posted) solves this question. I didn't read the paper, but the abstract only gave a looser bound that the sum of the first two eigenvalues is <= 2/sqrt(3) * n (and not just n).

a negative solution

The paper shows that the sum of the first two eigenvalues exceeds 1.125n - 25, so exceeds n when n is sufficiently large. Thus Nikiforov has given a negative solution to the problem. (Note: I have not checked the claims of the paper thoroughly.)

Is this really solved?

Yes. Nikiforov's inequality says that for all n >= 21 the maximum of the sum of the two largest eigenvalues of a graph on n vertices is at least f(n):=n(29+sqrt(329))/42-25. Notice that for n >= 204, f(n)-n is positive. Thus, for all n >= 204 there is a graph with n vertices and with the sum of the two largest eigenvalues greater than n.

Take a look at for an example and 3D picture of a graph on 40 vertices, with 770 edges for which the sum of the two largest eigenvalues is > 40.

I don't know if anyone knows the least n for which there is a graph with n vetices such that the sum of the two largest eigenvalues is greater than n.


Gary Davis

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.