**July 2, 2008**

The following graphs give counter-examples to Gernert’s conjecture for graphs with vertices, for though the examples do not have a connected complementary graph .

Together with Nikiforov’s 2006 paper:

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

and the recent (June 13, 2008 ) paper of Javad Ebrahimi, Bojan Mohar, Vladimir Nikiforov and Azhvan Sheikh Ahmady (eigenvalue_sum_extended), it’s beginning to look more likely that for all there is a graph on vertices with . As Bojan Mohar remarks, following the construction in his recent paper, for and sufficiently large, there is such a with conected.

*************

The graph with 37 vertices and 657 edges, and adjacency matrix that has zeros in the following places:

(1, 1), (2, 2), (2, 14), (2, 17), (2, 19), (2, 26), (2, 34), (2, 37), (3, 3), (4, 4), (5, 5), (6, 6), (6, 8), (7, 7), (8, 6), (8, 8), (9, 9), (9, 34), (10, 10), (11, 11), (12, 12), (12, 14), (13, 13), (14, 2), (14, 12), (14, 14), (15, 15), (16, 16), (17, 2), (17, 17), (18, 18), (19, 2), (19, 19), (20, 20), (21, 21), (22, 22), (23, 23), (24, 24), (25, 25), (26, 2), (26, 26), (27, 27), (28, 28), (29, 29), (30, 30), (31, 31), (32, 32), (33, 33), (34, 2), (34, 9), (34, 34), (35, 35), (36, 36), (37, 2), (37, 37)

has sum of the two largest eigenvalues .

It has characteristic polynomial

numerical spectrum (-3.08297, -2., -1.92919, -1.77378, -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.231694, -2.13825*10^-17, 7.84933*10^-17, 1.47326, 35.5444),

degree sequence (36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 35, 35, 35, 35, 35, 35, 35, 35, 34, 34, 30)

and energy .

The complement is disconnected:

*************

The graph with 36 vertices and 622 edges, and adjacency matrix that has zeros in the following places:

(1,1), (2,2), (3,3), (3,16), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9), (9,16), (9,33), (10,10), (11,11), (12,12), (13,13), (14,14), (15,15), (16,3), (16,9), (16,16), (16,19), (16,24), (16,35), (17,17), (18,18), (19,16), (19,19), (20,20), (21,21), (22,22), (23,23), (23,36), (24,16), (24,24), (24,33), (25,25), (26,26), (27,27), (28,28), (29,29), (30,30), (31,31), (32,32), (33,9), (33,24), (33,33), (34,34), (35,16), (35,35), (36,23), (36,36)

has sum of the two largest eigenvalues .

It has characteristic polynomial

numerical spectrum (-3.06372,-2.,-1.92434,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,-1.,1.42018,34.5817),

degree sequence (35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 34, 34, 34, 34, 34, 33, 33, 33, 30)

and energy .

The complement is disconnected:

*************

The graph with 34 vertices and 553 edges, and adjacency matrix that has zeros in the following places:

(1,1), (2,2), (3,3), (3,6), (4,4), (5,5), (6,3), (6,6), (6,11), (6,27), (7,7), (8,8), (9,9), (10,10), (10,27), (11,6), (11,11), (11,25), (12,12), (13,13), (14,14), (15,15), (16,16), (17,17), (18,18), (19,19), (20,20), (21,21), (22,22), (23,23), (24,24), (25,11), (25,25), (25,27), (26,26), (27,6), (27,10), (27,25), (27,27), (27,29), (27,30), (28,28), (29,27), (29,29), (30,27), (30,30), (31,31), (32,32), (33,33), (34,34)

has sum of the two largest eigenvalues .

It has characteristic polynomial

numerical spectrum (-3.03079, -2.13762, -1.60305, -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.396219, 0.10436, 1.5018, 32.5615),

degree sequence (33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 32, 32, 32, 32, 31, 31, 30, 28 )

and energy .

The complement is disconnected: