More spectral bounds on the clique and independence numbers
From MaRDI portal
Publication:1044204
DOI10.1016/j.jctb.2009.01.003zbMath1181.05072arXiv0706.0548MaRDI QIDQ1044204
Publication date: 11 December 2009
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0706.0548
05C35: Extremal problems in graph theory
05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
Related Items
Spectral radius and Hamiltonian properties of graphs, Eigenvalues and triangles in graphs, New analytical lower bounds on the clique number of a graph, On a generalization of the spectral Mantel's theorem, Refinement on Spectral Turán’s Theorem, Spectral condition for Hamiltonicity of a graph, Spectral analogues of Moon-Moser's theorem on Hamilton paths in bipartite graphs, Independent sets in graphs, The sharp lower bound for the spectral radius of connected graphs with the independence number, A simpler characterization of a spectral lower bound on the clique number, Spectral upper bounds for the order of a \(k\)-regular induced subgraph, The least eigenvalue of a graph with a given domination number, Ordering graphs with given size by their signless Laplacian spectral radii, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles, Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals, The signless Laplacian spectral radius of graphs with a prescribed number of edges, Bounds on the spectral radius of general hypergraphs in terms of clique number, Maximum degree and minimum degree spectral radii of some graph operations, Dimension-free bounds and structural results in communication complexity, Trees with small spectral gap
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds for the clique and the chromatic numbers of a graph
- On the independence number of random graphs
- Eigenvalue bounds for independent sets
- Spectral bounds for the clique and independence numbers of graphs
- The eigenvalues of random symmetric matrices
- On the independence and chromatic numbers of random regular graphs
- List coloring of random and pseudo-random graphs
- Bounds on graph eigenvalues. II
- The smallest eigenvalue of \(K_{r}\)-free graphs
- Laplacian spectral bounds for clique and independence numbers of graphs
- Some Inequalities for the Largest Eigenvalue of a Graph
- A proof of alon's second eigenvalue conjecture
- Maxima for Graphs and a New Proof of a Theorem of Turán