Spectral bounds for the clique and independence numbers of graphs (Q1079582)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Spectral bounds for the clique and independence numbers of graphs |
scientific article; zbMATH DE number 3963875
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Spectral bounds for the clique and independence numbers of graphs |
scientific article; zbMATH DE number 3963875 |
Statements
Spectral bounds for the clique and independence numbers of graphs (English)
0 references
1986
0 references
A sequence of bounds on the clique number of a graph is established. These depend on the eigenvalues and eigenvectors of the 0-1 adjacency matrix of the graph, and sharpen many existing spectral bounds. The proof lies on a result of \textit{T. S. Motzkin} and \textit{E. G. Straus} [Maxima for graphs and a new proof of a theorem of Turan, Can. J. Math. 17, 533- 540 (1965; Zbl 0129.399)] concerning the maximization of a certain quadratic form.
0 references
spectrum
0 references
independent set
0 references
clique number
0 references
eigenvalues
0 references
adjacency matrix
0 references
spectral bounds
0 references
