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

Citation

Cardoso DM & Rowlinson P (2010) Spectral upper bounds for the order of a k-regular induced subgraph. Linear Algebra and Its Applications, 433 (5), pp. 1031-1037. https://doi.org/10.1016/j.laa.2010.04.029

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.

Keywords
Graph; Main eigenvalue; Independence number; Clique number

Journal
Linear Algebra and Its Applications: Volume 433, Issue 5

People

Professor Peter Rowlinson

Emeritus Professor, Mathematics