| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4657412 | Journal of Combinatorial Theory, Series B | 2008 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
