×

zbMATH — the first resource for mathematics

The maximum clique and the signless Laplacian eigenvalues. (English) Zbl 1174.05079
Summary: Lower and upper bounds are obtained for the clique number \(\omega (G)\) and the independence number  \(\alpha (G)\), in terms of the eigenvalues of the signless Laplacian matrix of a graph \(G\).

MSC:
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDF BibTeX XML Cite
Full Text: DOI EuDML
References:
[1] D. Cvetković, M. Doob, H. Sachs: Spectra of Graphs, third ed. Johann Ambrosius Barth Verlag, Heidelberg-Leipzig, 1995.
[2] M. Desai, V. Rao: A characterization of the smallest eigenvalue of a graph. J. Graph Theory 18 (1994), 181–194. · Zbl 0792.05096
[3] W. Haemers: Interlacing eigenvalues and graphs. Linear Algebra Appl. 227–228 (1995), 593–616. · Zbl 0831.05044
[4] W. Haemers, E. Spence: Enumeration of cospectral graph. Europ. J. Combin. 25 (2004), 199–211. · Zbl 1033.05070
[5] M. Lu, H. Liu, F. Tian: Laplacian spectral bounds for clique and independence numbers of graphs. J. Combin. Theory Ser. B 97 (2007), 726–732. · Zbl 1122.05072
[6] T. Motzkin, E. G. Straus: Maxima for graphs and a new proof of a theorem of Turén. Canad. J. Math. 17 (1965), 533–540. · Zbl 0129.39902
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.