Eigenvalue bounds for independent sets
From MaRDI portal
Publication:933677
DOI10.1016/j.jctb.2007.10.007zbMath1156.05041arXivmath/0508081OpenAlexW1986323939MaRDI QIDQ933677
Michael W. Newman, Chris D. Godsil
Publication date: 24 July 2008
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0508081
Related Items (41)
Toughness and normalized Laplacian eigenvalues of graphs ⋮ Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software ⋮ Triangle-free induced subgraphs of the unitary polarity graph ⋮ A note on Erdős-Ko-Rado sets of generators in Hermitian polar spaces ⋮ Spectra and Laplacian spectra of arbitrary powers of lexicographic products of graphs ⋮ Laplacian spectral bounds for clique and independence numbers of graphs ⋮ Spectral Bounds for the k-Regular Induced Subgraph Problem ⋮ The independence number for polarity graphs of even order planes ⋮ Hoffman's ratio bound ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ Constructing uniquely realizable graphs ⋮ A recursive construction of the regular exceptional graphs with least eigenvalue \(-2\) ⋮ The power of small coalitions under two-tier majority on regular graphs ⋮ A note on eigenvalue bounds for independence numbers of non-regular graphs ⋮ Approximately counting independent sets in bipartite graphs via graph containers ⋮ Spectral bounds for the vulnerability parameters of graphs ⋮ On the independence number of regular graphs of matrix rings ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Theorems of Erdős-Ko-Rado type in geometrical settings ⋮ Graph toughness from Laplacian eigenvalues ⋮ On a conjecture of Erdős and Simonovits: even cycles ⋮ Unnamed Item ⋮ Independent sets in graphs ⋮ Cameron-Liebler sets of \(k\)-spaces in \(\mathrm{PG}(n,q)\) ⋮ The least eigenvalue of a graph with a given domination number ⋮ A simpler characterization of a spectral lower bound on the clique number ⋮ The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph ⋮ Spectral upper bounds for the order of a \(k\)-regular induced subgraph ⋮ The \(k\)-regular induced subgraph problem ⋮ Orthogonal Polarity Graphs and Sidon Sets ⋮ On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs ⋮ Hamiltonian \(s\)-properties and eigenvalues of \(k\)-connected graphs ⋮ More spectral bounds on the clique and independence numbers ⋮ A relative bound for independence ⋮ The maximum spectral radius of non-bipartite graphs forbidding short odd cycles ⋮ Dual Hoffman Bounds for the Stability and Chromatic Numbers Based on Semidefinite Programming ⋮ Cops and Robbers on Graphs Based on Designs ⋮ On the chromatic number of the Erdős-Rényi orthogonal polarity graph ⋮ A new eigenvalue bound for independent sets ⋮ The product of two high-frequency graph Laplacian eigenfunctions is smooth ⋮ An Erdős-Ko-Rado theorem for finite classical polar spaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Graphs from projective planes
- Problems in algebraic combinatorics
- Graphs and Hermitian matrices: eigenvalue interlacing
- Graphs without quadrilaterals
- On the number of edges of quadrilateral-free graphs
- Laplacian spectral bounds for clique and independence numbers of graphs
- Eigenvalues of the Laplacian of a graph∗
- On Graphs that do not Contain a Thomsen Graph
This page was built for publication: Eigenvalue bounds for independent sets
