Article
Details
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
Status | Published |
---|---|
Publication date | 31/10/2010 |
URL | |
Publisher | Elsevier |
ISSN | 0024-3795 |
People (1)
Emeritus Professor, Mathematics