Abstract: We prove an upper bound for the independence number of a graph in terms of the largest Laplacian eigenvalue, and of a certain induced subgraph. Our bound is a refinement of a well-known Hoffman-type bound.
Recommendations
Cites work
- scientific article; zbMATH DE number 3623619 (Why is no real title available?)
- Eigenvalue bounds for independent sets
- Graphs with constant \(\mu\) and \(\overline{\mu}\)
- Interlacing eigenvalues and graphs
- Laplacian spectral bounds for clique and independence numbers of graphs
- On Graphs that do not Contain a Thomsen Graph
- On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs
- On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
- On the two conjectures of Graffiti
- The independence number for polarity graphs of even order planes
Cited in
(11)- Eigenvalue bounds for independent sets
- Hoffman's ratio bound
- Upper bounds on the independence and the clique covering number
- Bounded Independence Fools Halfspaces
- Tight Probability Bounds with Pairwise Independence
- On the independence number of regular graphs of matrix rings
- scientific article; zbMATH DE number 5074407 (Why is no real title available?)
- Weighted matrix eigenvalue bounds on the independence number of a graph
- Study on the upper bound of the dependence number
- Around -independence
- A graph for which the inertia bound is not tight
This page was built for publication: A relative bound for independence
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2329192)
