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 with vertices and edges, and adjacency matrix:

has .

The characteristic polynomial is 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 .

The graph is, therefore, not isomorphic with

2. The graph with vertices and edges with the following adjacency matrix:

has .

The characteristic polynomial is 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 .

The graph is, therefore, not isomorphic with or with .

3. The graph with vertices and edges with the following adjacency matrix:

has .

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 .

The graph is, therefore, not isomorphic with or .

4. The graph with vertices and edges with the following adjacency matrix:

has .

The characteristic polynomial is 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 .

The graph is, therefore, not isomorphic with , or

An example of a graph with and is with the following adjacency matrix and 3-dimensional representation:

The characteristic polynomial is 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 .

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 , looked for one with .

Using the same strategy I found a graph with vertices, edges, and . 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 , 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 . 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 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 vertices and . Add one isolated vertex (or join it to the graph by one edge if you wish). This will make the complement connected but will not change much if is large.”