Sum of largest two eigenvalues of a simple graph.1

The largest two, necessarily real, eigenvalues of a simple graph play a significant role in the energy of . The largest eigenvalue is bounded below by where is the number of vertices and the number of edges of . The largest eigenvalue features in Koolen & Moulton’s proof of the upper bound . Some knowledge of the second largest eigenvalue might go some way toward sharpening this upper bound for in those – mostly common -cases in which this upper bound is not attained.

Dieter Gernert has proposed that the sum of the largest two eigenvalues of a simple graph on vertices should be bounded above by . 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 , with 40 vertices and 770 edges, whose adjacency matrix and – rather uninformative though beautiful – 3-dimensional representation appear below, has a sum of for the sum of its two largest eigenvalues:

The characteristic polynomial is 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 which is of the Koolen-Moulten upper bound for the energy of a graph with vertices and edges.

A statistical analysis of for graphs with vertices and edges shows a very skewed distribution with a large mean and large standard deviation :

Occasionally, but apparently rarely, despite the large standard deviation, is negative, as it is for .

Postscript: I just found this question has been answered. A definitive paper, on the existence of graphs with 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 for shows that for all there is a graph with .

Given the existence of , what is the minimal for which there is a graph on vertices with ?

Given Nikiforov’s construction, Dieter Gernert has modified his question to: “Is is true that for all connected graphs with vertices and connected complementary graph ?” Dieter conjectures this is true.