Sum of largest two eigenvalues of a simple graph.3 « Things I’m working on and thinking about… Gary E. Davis

Sum of largest two eigenvalues of a simple graph.3

July 2, 2008 · Leave a Comment

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:

Categories: Uncategorized

0 responses so far ↓

There are no comments yet...Kick things off by filling out the form below.

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