Spectral bounds for the clique and independence numbers of graphs
From MaRDI portal
Publication:1079582
DOI10.1016/0095-8956(86)90069-9zbMath0598.05047OpenAlexW1977170634MaRDI QIDQ1079582
Publication date: 1986
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(86)90069-9
Paths and cycles (05C38) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18)
Cites Work
Related Items (92)
Spectral extremal graphs for intersecting cliques ⋮ A Motzkin-Straus type result for 3-uniform hypergraphs ⋮ The spectral radius of graphs with no intersecting odd cycles ⋮ Generalizing theorems of Nosal and Nikiforov: triangles and quadrilaterals ⋮ Walks and the spectral radius of graphs ⋮ Laplacian spectral bounds for clique and independence numbers of graphs ⋮ Cliques and the spectral radius ⋮ A spectral condition for the existence of the square of a path ⋮ Three conjectures in extremal spectral graph theory ⋮ A note on eigenvalues of signed graphs ⋮ On the spectral radius of graphs without a star forest ⋮ The maximum spectral radius of wheel-free graphs ⋮ A unique characterization of spectral extrema for friendship graphs ⋮ Spectral extrema of \(K_{s,t}\)-minor free graphs -- on a conjecture of M. Tait ⋮ A homogeneous polynomial associated with general hypergraphs and its applications ⋮ Hardness results and spectral techniques for combinatorial problems on circulant graphs ⋮ Inequalities for the number of walks in graphs ⋮ A sharp upper bound on the spectral radius of \(C_5\)-free/\(C_6\)-free graphs with given size ⋮ New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix ⋮ On a conjecture of Nikiforov involving a spectral radius condition for a graph to contain all trees ⋮ The maximum spectral radius of \(\{C_3, C_5\}\)-free graphs of given size ⋮ A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs ⋮ On the \(A_\alpha \)-spectral radius of graphs with given size ⋮ A note on eigenvalue bounds for independence numbers of non-regular graphs ⋮ Spectral extremal graphs for the bowtie ⋮ Matrix power inequalities and the number of walks in graphs ⋮ A Spectral Erdős-Sós Theorem ⋮ Extremal problems for the \(p\)-spectral radius of graphs ⋮ Extensions on spectral extrema of \(C_5/C_6\)-free graphs with given size ⋮ Refinement on Spectral Turán’s Theorem ⋮ An \(A_\alpha\)-spectral Erdős-Pósa theorem ⋮ On \(A_{\alpha}\) spectral extrema of graphs forbidding even cycles ⋮ Two conjectured strengthenings of Turán's theorem ⋮ Spectral radius conditions for the existence of all subtrees of diameter at most four ⋮ On graphs with eigenvectors in \(\{-1,0,1\}\) and the max \(k\)-cut problem ⋮ On the first two eigenvalues of regular graphs ⋮ A note on the spectral characterization of strongly connected bicyclic digraphs ⋮ Remarks on the largest eigenvalue of a signed graph ⋮ The index of signed graphs with forbidden subgraphs ⋮ The bipartite Turán number and spectral extremum for linear forests ⋮ Extremal results for \(C_3^-\)-free signed graphs ⋮ Spectral Turán problems for intersecting even cycles ⋮ Spectral extremal problem on disjoint color-critical graphs ⋮ An \(A_{\alpha}\)-spectral Erdős-Sós theorem ⋮ Spectral radius of digraphs with given dichromatic number ⋮ The maximum spectral radius of graphs of given size with forbidden subgraph ⋮ A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs ⋮ Unnamed Item ⋮ Bounds on the spectral radius of general hypergraphs in terms of clique number ⋮ On graphs with adjacency and signless Laplacian matrices eigenvectors entries in \(\{-1,+1\}\) ⋮ Bounds on graph eigenvalues. II ⋮ On Lagrangians of \(r\)-uniform hypergraphs ⋮ The spectral even cycle problem ⋮ Adjacency eigenvalues of graphs without short odd cycles ⋮ The spectral radius of graphs with no odd wheels ⋮ Spectral extremal graphs without intersecting triangles as a minor ⋮ A spectral condition for odd cycles in non-bipartite graphs ⋮ Analytic methods for uniform hypergraphs ⋮ Spectral radius of strongly connected digraphs ⋮ A simpler characterization of a spectral lower bound on the clique number ⋮ Chromatic number and signless Laplacian spectral radius of graphs ⋮ The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph ⋮ Maximum spectral radius of graphs with given connectivity, minimum degree and independence number ⋮ The signless Laplacian spectral radius of graphs with no intersecting triangles ⋮ Eigenvalues and chromatic number of a signed graph ⋮ Independence number and spectral radius of cactus graphs ⋮ Spectral extremal results on trees ⋮ Measure-theoretic bounds on the spectral radius of graphs from walks ⋮ Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs ⋮ Some Motzkin-Straus type results for non-uniform hypergraphs ⋮ A spectral Erdős-Rademacher theorem ⋮ The minimum spectral radius for \(K_{r+1}\)-saturated graphs with \(r = 4\), 5 ⋮ Matchings in regular graphs from eigenvalues ⋮ Spectral extrema of graphs with fixed size: forbidden triangles and pentagons ⋮ On the spectral radius of graphs without a gem ⋮ Turán's theorem implies Stanley's bound ⋮ Spectral extremal results for hypergraphs ⋮ Exact bounds on the order of the maximum clique of a graph. ⋮ The largest eigenvalue of a graph: A survey ⋮ A generalization of the Motzkin-Straus theorem to hypergraphs ⋮ The minimum spectral radius of graphs with a given independence number ⋮ The spectral radius of graphs with given independence number ⋮ Eigenvalues and triangles in graphs ⋮ On graph Laplacian eigenvectors with components in \(\{- 1, 0, 1 \}\) ⋮ More spectral bounds on the clique and independence numbers ⋮ Spectral extrema of graphs: forbidden hexagon ⋮ The maximum spectral radius of non-bipartite graphs forbidding short odd cycles ⋮ Continuous cubic formulations for cluster detection problems in networks ⋮ GRAPHS WITH SMALL INDEPENDENCE NUMBER MINIMIZING THE SPECTRAL RADIUS ⋮ A new eigenvalue bound for independent sets ⋮ The maximum clique problem ⋮ New analytical lower bounds on the clique number of a graph
This page was built for publication: Spectral bounds for the clique and independence numbers of graphs
