Spectral upper bounds for the order of a k-regular induced subgraph

Abstract

Let G be a simple graph with least eigenvalue λ and let S be a set of vertices in G which induce a subgraph with mean degree k. We use a quadratic programming technique in conjunction with the main angles of G to establish an upper bound of the form | S | ≤ inf {(k + t) qG (t) : t > - λ} where qG is a rational function determined by the spectra of G and its complement. In the case k = 0 we obtain improved bounds for the independence number of various benchmark graphs. © 2010 Elsevier Inc. All rights reserved.