A simpler characterization of a spectral lower bound on the clique number

DOI10.1007/s00186-009-0295-4zbMath1259.05133OpenAlexW2078573010MaRDI QIDQ966428

E. Alper Yıldırım

Publication date: 23 April 2010

Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00186-009-0295-4

zbMATH Keywords

quadratic programmingadjacency matrixlower boundspectral decompositionclique numbercomputational resultsspectral lower bounds

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Eigenvalue bounds for independent sets
• More spectral bounds on the clique and independence numbers
• Spectral bounds for the clique and independence numbers of graphs
• Geometric algorithms and combinatorial optimization
• Evolution towards the maximum clique
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Exact bounds on the order of the maximum clique of a graph.
• The smallest eigenvalue of \(K_{r}\)-free graphs
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• Laplacian spectral bounds for clique and independence numbers of graphs
• Maxima for Graphs and a New Proof of a Theorem of Turán

This page was built for publication: A simpler characterization of a spectral lower bound on the clique number