Spectral upper bounds for the order of a k-regular induced subgraph
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...
| Autor principal: | |
|---|---|
| Outros Autores: | |
| Formato: | article |
| Idioma: | eng |
| Publicado em: |
1000
|
| Assuntos: | |
| Texto completo: | http://hdl.handle.net/10773/4234 |
| País: | Portugal |
| Oai: | oai:ria.ua.pt:10773/4234 |
| Resumo: | 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. |
|---|