Eigenvalue bounds for independent sets

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We derive bounds on the size of an independent set based on eigenvalues. This generalizes a result due to Delsarte and Hoffman. We use this to obtain new bounds on the independence number of the Erdős-Rényi graphs. We investigate further properties of our bounds, and show how our results on the Erdős-Rényi graphs can be extended to other polarity graphs.
18 pages

Keywords

Combinatorics, 05C69; 51E15, 51E12

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/75975

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0508081
 http://arxiv.org/abs/math/0508081

Collections

arXiv