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

DOI10.1016/J.DAM.2014.04.008MaRDI QIDQ400541zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3232670 (Why is no real title available?)
• Eigenvalue bounds for independent sets
• Eigenvectors and eigenvalues of non-regular graphs
• Explicit construction of linear sized tolerant networks
• Extreme eigenvalues of nonregular graphs
• Interlacing eigenvalues and graphs
• Norm-graphs: Variations and applications
• On the independence number of the Erdős‐Rényi and projective norm graphs and a related hypergraph
• On the spectrum of projective norm-graphs
• Proofs from THE BOOK
• Quasi-random graphs
• Spectral bounds for the clique and independence numbers of graphs
• The largest eigenvalue 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)