A new eigenvalue bound for independent sets

DOI10.1016/J.DISC.2014.12.008MaRDI QIDQ2346340zbMATH OpenOpenAlexFDO

Authors Jochen Harant, Sebastian Richter

Publication date 1 June 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2014.12.008

zbMATH Keywords

eigenvaluesindependence number

Mathematics Subject Classification ID

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

Recommendations

• Eigenvalue bounds for independent sets
• A note on eigenvalue bounds for independence numbers of non-regular graphs
• Bounds for eigenvalues of parameter-dependent matrices
• New bounds for the minimum eigenvalue of M-matrices
• Independence number and the normalized Laplacian eigenvalue one
• Weighted matrix eigenvalue bounds on the independence number of a graph
• New bound on eigenvalue of the Hadamard product of matrices
• Bounds for the eigenvalues of matrices
• An improved upper bound for the number of distinct eigenvalues of a matrix after perturbation
• Bounds on eigenvalues and chromatic numbers

Cites work

• A course in combinatorics.
• Eigenvalue bounds for independent sets
• Eigenvalues of the Laplacian of a graph^∗
• Foreword: Special issue on stability in graphs and related topics
• Graphs and Hermitian matrices: eigenvalue interlacing
• scientific article; zbMATH DE number 3668628 (Why is no real title available?)
• scientific article; zbMATH DE number 740754 (Why is no real title available?)
• scientific article; zbMATH DE number 878889 (Why is no real title available?)
• scientific article; zbMATH DE number 3377258 (Why is no real title available?)
• Interlacing eigenvalues and graphs
• Interlacing for weighted graphs using the normalized Laplacian
• Spectral bounds for the clique and independence numbers of graphs
• The critical independence number and an independence decomposition
• The Gewirtz graph: An exercise in the theory of graph spectra

Cited in

(11)

• -connectivity, integrity, tenacity, toughness and eigenvalues of graphs
• Toughness and normalized Laplacian eigenvalues of graphs
• Laplacian eigenvalue distribution and graph parameters
• A relative bound for independence
• Eigenvalue conditions for induced subgraphs
• A note on eigenvalue bounds for independence numbers of non-regular graphs
• Spectral bounds for the vulnerability parameters of graphs
• Toughness, Hamiltonicity and eigenvalues of graphs
• Some results on the k-alliance and domination of graphs
• Unified bounds for the independence number of graphs
• Eigenvalue bounds for independent sets

This page was built for publication: A new eigenvalue bound for independent sets

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