Sum of largest two eigenvalues of a simple graph.3

July 2, 2008

The following graphs give counter-examples to Gernert’s conjecture \lambda_1+\lambda_2 \leq n for graphs \Gamma with n vertices, for n = 34, 36, 37 though the examples do not have a connected complementary graph \Gamma^{\circ}.

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 n \geq 21 there is a graph \Gamma on n vertices with \lambda_1 + \lambda > n. As Bojan Mohar remarks, following the construction in his recent paper, for n \equiv 0 \textrm{ (mod 7)} and sufficiently large, there is such a \Gamma with \Gamma^{\circ} 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 \lambda_1 +\lambda_2 \approx 37.0176 > 37.

It has characteristic polynomial -x^2(1+x)^28(2+x)(128+642x+344x^2-226x^3-191x^4-30x^5+x^6)

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 \approx 74.0353.

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 \lambda_1 +\lambda_2 \approx 36.0019 > 36.

It has characteristic polynomial x(1+x)^29(2+x)(4+290x+31x^2-125x^3-31x^4+x^5)

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 \approx 57.98994.

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 \lambda_1 +\lambda_2 \approx 34.063309767691338026 > 34.

It has characteristic polynomial (1+x)^27(-21+133x+622x^2+328x^3-209x^4-175x^5-27x^6+x^7)

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 \approx 68.3353.

The complement is disconnected:

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