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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s