Article ID Journal Published Year Pages File Type
6416434 Linear Algebra and its Applications 2014 15 Pages PDF
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
, ,