# Sum of largest two eigenvalues of a simple graph.1

The largest two, necessarily real, eigenvalues of a simple graph $\Gamma$ play a significant role in the energy $E(\Gamma)$ of $\Gamma$. The largest eigenvalue $\lambda_1$ is bounded below by $\frac{2e}{v}$ where $v$ is the number of vertices and $E$ the number of edges of $\Gamma$. The largest eigenvalue features in Koolen & Moulton’s proof of the upper bound $E(\Gamma) \leq \frac{2e}{v}+\sqrt{(v-1)(2e-(\frac{2e}{v})^2)}$. Some knowledge of the second largest eigenvalue $\lambda_2$ might go some way toward sharpening this upper bound for $E(\Gamma)$ in those – mostly common -cases in which this upper bound is not attained.

Dieter Gernert has proposed that the sum $\lambda_1 + \lambda_2$ of the largest two eigenvalues of a simple graph on $v$ vertices should be bounded above by $v$. As he points out on the Spectral Graph Theory page, this is certainly true for regular graphs, and has also been proved for some special classes of graphs such as planar, toroidal, completely multipartite, and triangular-free graphs.

However, the graph $\Gamma_1(40,770)$, with 40 vertices and 770 edges, whose adjacency matrix and – rather uninformative though beautiful – 3-dimensional representation appear below, has a sum of $\approx 40.0032 > 40$ for the sum of its two largest eigenvalues:

The characteristic polynomial is $x(1+x)^{31}(-132-496x+1106x^2+1716x^3+120x^4-620x^5-274x^6-31x^7+x^8)$ and the sorted numerical spectrum is (-3.02512, -2.47643, -1.93174, -1.8057, -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -1., -0.202583, -6.38638×10-17, 0.438356, 1.47645, 38.5268)

The graph has (sorted) degree sequence (39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 38, 38, 38, 38, 38, 38, 38, 38, 38, 37, 35, 34).

The energy is $E(\Gamma_1(40,770)) \approx 80.8831$ which is $\approx 94.1\%$ of the Koolen-Moulten upper bound $\frac{2e}{v}+\sqrt{(v-1)(2e-(\frac{2e}{v})^2)}$ for the energy of a graph with $v=40$ vertices and $e=770$ edges.

A statistical analysis of $v-(\lambda_1+\lambda_2)$ for graphs with $13 \leq v \leq 60$ vertices and $v-1 \leq e \leq \frac{1}{2}v(v-1)-1$ edges shows a very skewed distribution with a large mean $\approx 9$ and large standard deviation $\approx 6$:

Occasionally, but apparently rarely, despite the large standard deviation, $v-(\lambda_1+\lambda_2)$ is negative, as it is for $\Gamma_1(40,770)$.

Postscript: I just found this question has been answered. A definitive paper, on the existence of graphs with $v< (\lambda_1+\lambda_2)$ is:

Nikiforov, V. (2006) Linear combinations of graph eigenvalues. Electronic Journal of Linear Algebra, 15, 329-336. (nikiforov-sums_of_graph_eigenvalues)

Nikiforov’s inequality $max(\lambda_1+\lambda_2) >\frac{29 + \sqrt(329)}{42}v -25$ for $v \geq 21$ shows that for all $v \geq 205$ there is a graph with $\lambda_1+\lambda_2 > v$ .

Given the existence of $\Gamma_1(40,770)$, what is the minimal $v$ for which there is a graph on $v$ vertices with $\lambda_1 + \lambda_2 > v$?

Given Nikiforov’s construction, Dieter Gernert has modified his question to: “Is is true that $\lambda_1+\lambda_2 \leq v$ for all connected graphs $\Gamma$ with $v$ vertices and connected complementary graph $\Gamma^{\circ}$?” Dieter conjectures this is true.