Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6416434 | Linear Algebra and its Applications | 2014 | 15 Pages |
Abstract
Let G be a graph of order n and let μ1(G)⩾â¯â©¾Î¼n(G) be the eigenvalues of its adjacency matrix. This note studies eigenvalue problems of Nordhaus-Gaddum type. Let G¯ be the complement of a graph G. It is shown that if s⩾2 and n⩾15(sâ1), then|μs(G)|+|μs(G¯)|⩽n/2(sâ1)â1.Also if s⩾1 and n⩾4s, then|μnâs+1(G)|+|μnâs+1(G¯)|⩽n/2s+1. If s=2k+1 for some integer k, these bounds are asymptotically tight. These results settle infinitely many cases of a general open problem.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Vladimir Nikiforov, Xiying Yuan,