Skip header navigation
×

Article

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

StatusPublished
Author(s)Cardoso, Domingos M; Rowlinson, Peter
Publication date31/10/2010
URLhttp://hdl.handle.net/1893/18501
PublisherElsevier
ISSN0024-3795
Scroll back to the top