Title of article
Eigenvalue bounds for independent sets
Author/Authors
Godsil، نويسنده , , C.D. and Newman، نويسنده , , M.W.، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2008
Pages
14
From page
721
To page
734
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.
Keywords
independent sets , Delsarte–Hoffman bound , loops , polarity graph
Journal title
Journal of Combinatorial Theory Series B
Serial Year
2008
Journal title
Journal of Combinatorial Theory Series B
Record number
1528723
Link To Document