Things I’m working on and thinking about… Gary E. Davis

Sum of largest two eigenvalues of a simple graph.2

June 30, 2008 · Leave a Comment

Below are several other examples of non-isomorphic graphs with 40 vertices, 770 edges, and sum of the two largest eigenvalues > 40. None of these has a connected complement.

1. The graph \Gamma_2(40,770) with v=40 vertices and e = 770 edges, and adjacency matrix:

has \lambda_1+\lambda_2 \approx 40.0086 > v=40.

The characteristic polynomial is x(1+x)^31 (-68-393x+1131x^2 +1681x^3 +101x^4-622x^5 -274x^6-31x^7+x^8) and the sorted numerical spectrum is (-3.10756, -2.32462, -1.93923, -1.85196, -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.132379, -4.09544*10^-16, 0.347119, 1.48047, 38.5282).

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, 37, 37, 37, 33).

The energy is E(\Gamma_2(40,770)) \approx 80.7115.

The graph \Gamma_2(40,770) is, therefore, not isomorphic with \Gamma_1(40,772)

2. The graph\Gamma_3(40,770) with v=40 vertices and e=770 edges with the following adjacency matrix:

has \lambda_1+\lambda_2 \approx 40.0284 > 40.

The characteristic polynomial is x^2(1+x)^29(2+x)(-50+271x +1577x^2+1506x^3 -74x^4 -649x^5-273x^6-31x^7+x^8) and the sorted numerical spectrum is (-3.13442, -2.13787, -2., -1.86594, -1.60276, -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.396136, -8.94552*10^-17, 1.54841*10^-16, 0.108693, 1.50412, 38.5243).

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, 37, 37, 37, 33).

The energy is E(\Gamma_3(40,770)) \approx 80.2743.

The graph \Gamma_3(40,770) is, therefore, not isomorphic with \Gamma_1(40,772) or with \Gamma_2(40,772).

3. The graph\Gamma_4(40,770) with v=40 vertices and e=770 edges with the following adjacency matrix:

has \lambda_1+\lambda_2 \approx 40.0473 > 40.

The characteristic polynomial is $latex(1+x)^31(33-137x-454x^2+1202x^3 +1783x^4+139x^5 -618x^6-274x^7-31x^8+x^9)$ and the sorted numerical spectrum is (-3.04901, -2.30734, -2.20329, -1.65743, -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.346656, 0.199239, 0.317189, 1.52195, 38.5253).

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, 37, 37, 37, 33).

The energy is E(\Gamma_3(40,770)) \approx 81.1274.

The graph \Gamma_4(40,770) is, therefore, not isomorphic with \Gamma_1(40,772), \Gamma_2(40,770) or \Gamma_3(40,772).

4. The graph\Gamma_5(40,770) with v=40 vertices and e=770 edges with the following adjacency matrix:

has \lambda_1+\lambda_2 \approx 40.0716> 40.

The characteristic polynomial is x(1+x)^31(-132-296x+1318x^2+1776x^3+ 122x^4- 620x^5-274x^6-31x^7+x^8) and the sorted numerical spectrum is (-3.12149, -2.35749, -1.92974, -1.75915, -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.253681, 1.79662*10^-17, 0.349958, 1.54489, 38.5267).

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, 39, 39, 38, 38, 38, 38, 38, 37, 36, 36, 36, 35).

The energy is E(\Gamma_3(40,770)) \approx 80.8431.

The graph \Gamma_5(40,770) is, therefore, not isomorphic with \Gamma_1(40,772), \Gamma_2(40,770), \Gamma_3(40,772) or \Gamma_4(40,772)

An example of a graph with v = 39, e = 731 and \lambda_1+\lambda_2 \approx 39.0523 > 39 is \Gamma_1(39,731) with the following adjacency matrix and 3-dimensional representation:

The characteristic polynomial is -x(1+x)^30(2+x)(-4-164x+674x^2+523x^3-196x^4 -202x^5-32x^6+x^7) and the sorted numerical spectrum is (-3.08933, -2.24518, -2., -1.92719, -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.0223697, -4.2055*10^-16, 0.231765, 1.53858, 37.5137).

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

The energy is E(\Gamma_1(39,731) \approx 78.5681.

A 3 dimensional representation of the complementray graph is:

The vetcies apparently connected at the bottom left are in fact not connected, as the following, more prosaic, view shows:

I found this example by looking for a graph with 39 vertices, and taking a cue from \Gamma_1(40,770), looked for one with e \approx \frac{1}{2}39\times 38 \times \frac{770}{780} = 731.5.

Using the same strategy I found a graph \Gamma_1(38,694) with v= 38 vertices, e = 694 edges, and \lambda_1+\lambda_2 \approx 38.0326> 38. Apart from the diagonal the 0 entries in the adjacency matrix are in the following positions:

(5, 19), (8, 32), (9, 32), (14, 30), (14, 32), (16, 26), (19, 5), (19, 30), (19, 32), (19, 33), (26, 16),(30, 14), (30, 19),(32, 8), (32, 9), (32, 14), (32, 19), (33, 19).

The characteristic polynomial is x(1+x)^29(-1-3x+x^2+x^3)(48-297x- 484x^2-226x^3- 30x^4+x^5), the numerical spectrum (-3.06878, -2.17009, -1.92725, -1.68699, -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.311108, 2.86673*10^-16, 0.13162, 1.48119, 36.5514),the degree sequence (37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 36, 36, 36, 36, 36, 36, 35, 35, 33, 33) and the energy \approx 76.3284. Again, the complementary graph is disconnected:

Bojan Mohar just sent me a copy of his paper “On the sum of two largest eigenvalues of a symmetric matrix” (June 13, 2008 ) with Javad Ebrahimi, Vladimir Nikiforov and Azhvan Sheikh Ahmady.

Here’s the abstract:

D. Gernert conjectured that the sum of two largest eigenvalues of the adjacency matrix of any simple graph is at most the number of vertices of the graph. This can be proved, in particular, for all regular graphs. Gernert’s conjecture was recently disproved by one of the authors, who also provided a nontrivial upper bound for the sum of two largest eigenvalues. In this paper we improve the lower and upper bounds to near-optimal ones, and extend results from graphs to general non-negative matrices.

Here’s a pdf version of the paper: eigenvalue_sum_extended

Bojan Mohar comments (July 1, 2008 ) that Dieter Gernert’s modified conjecture cannot hold: “the proof towards the end of the paper shows that largest \lambda_1+ \lambda_2 is achieved when the complement is bipartite and (most likely) has several isolated vertices. The updated conjecture seems in a good direction but it is wrong again: Take our example (same paper) with 7n vertices and \tau_2 = \frac{8}{7} . Add one isolated vertex (or join it to the graph by one edge if you wish). This will make the complement connected but \tau_2 will not change much if n is large.”

Categories: Uncategorized