Yes. Nikiforov's inequality says that for all n >= 21 the maximum of the sum of the two largest eigenvalues of a graph on n vertices is at least f(n):=n(29+sqrt(329))/42-25. Notice that for n >= 204, f(n)-n is positive. Thus, for all n >= 204 there is a graph with n vertices and with the sum of the two largest eigenvalues greater than n.
Take a look at http://garyedavis.wordpress.com/ for an example and 3D picture of a graph on 40 vertices, with 770 edges for which the sum of the two largest eigenvalues is > 40.
I don't know if anyone knows the least n for which there is a graph with n vetices such that the sum of the two largest eigenvalues is greater than n.
login/create account
Drupal
CSI of Charles University
Is this really solved?
Yes. Nikiforov's inequality says that for all n >= 21 the maximum of the sum of the two largest eigenvalues of a graph on n vertices is at least f(n):=n(29+sqrt(329))/42-25. Notice that for n >= 204, f(n)-n is positive. Thus, for all n >= 204 there is a graph with n vertices and with the sum of the two largest eigenvalues greater than n.
Take a look at http://garyedavis.wordpress.com/ for an example and 3D picture of a graph on 40 vertices, with 770 edges for which the sum of the two largest eigenvalues is > 40.
I don't know if anyone knows the least n for which there is a graph with n vetices such that the sum of the two largest eigenvalues is greater than n.
Regards,
Gary Davis