A note on eigenvalue bounds for independence numbers of non-regular graphs

DOI10.1016/J.DAM.2014.04.008zbMATH Open1297.05148OpenAlexW1974676765MaRDI QIDQ400541FDOQ400541

Authors: Yusheng Li, Zhen Zhang 

Publication date: 22 August 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2014.04.008

Recommendations

• Extreme eigenvalues of nonregular graphs
• A new eigenvalue bound for independent sets
• New bounds on the independence number of connected graphs
• A generalization for the clique and independence numbers
• An improved lower bound on the independence number of a graph

zbMATH Keywords

independence numbereigenvalue boundsimple non-regular graph

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cites Work

• Title not available (Why is that?)
• Interlacing eigenvalues and graphs
• Title not available (Why is that?)
• Eigenvalue bounds for independent sets
• Title not available (Why is that?)
• Quasi-random graphs
• Explicit construction of linear sized tolerant networks
• Norm-graphs: Variations and applications
• Title not available (Why is that?)
• Proofs from THE BOOK
• On the spectrum of projective norm-graphs
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• Spectral bounds for the clique and independence numbers of graphs
• The largest eigenvalue of nonregular graphs
• Eigenvectors and eigenvalues of non-regular graphs
• Extreme eigenvalues of nonregular graphs

Cited In (5)

• A new eigenvalue bound for independent sets
• Combinatorial upper bounds for the smallest eigenvalue of a graph
• A bound on the spectral radius of graphs in terms of their Zagreb indices
• Topological bounds for graph representations over any field
• Independent sets in graphs

This page was built for publication: A note on eigenvalue bounds for independence numbers of non-regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400541)