Eigenvalue bounds for independent sets

2005/08/03 by Chris Godsil, C. D. Godsil, Michael Newman +3 · 1 citation
Computer Science · Mathematics · #05C69 #51E12 #51E15 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C69 #msc:51E12 #msc:51E15

paper · pdf · doi:10.48550/arxiv.math/0508081

18 pages

arxiv created 2005/08/03 · openalex publication_date 2005/08/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Laplacian Bounds for the Dissociation Number of Regular Graphs of Matrix Rings

Related

• Independent sets in polarity graphs
• More spectral bounds on the clique and independence numbers
• On the independence number of graphs related to a polarity
• Optimization of eigenvalue bounds for the independence and chromatic number of graph powers
• Large independent sets from local considerations