×

Laplacian spectral bounds for clique and independence numbers of graphs. (English) Zbl 1122.05072

Summary: We present lower and upper bounds for the independence number \(\alpha (G)\) and the clique number \(\omega (G)\) involving the Laplacian eigenvalues of the graph \(G\).

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Chung, F. R.K., Diameters and eigenvalues, J. Amer. Math. Soc., 2, 187-196 (1989) · Zbl 0678.05037
[2] Chung, F. R.K.; Faber, V.; Manteuffel, T. A., An upper bound on the diameter of a graph from eigenvalues, SIAM J. Discrete Math., 7, 443-457 (1994) · Zbl 0808.05072
[3] Cvetković, D.; Doob, M.; Sachs, H., Spectra of Graphs (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[4] Fiedler, M., Algebraic connectivity of graphs, Czechoslovak Math. J., 3, 98, 298-305 (1973) · Zbl 0265.05119
[5] C.D. Godsil, M.W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, in press; C.D. Godsil, M.W. Newman, Eigenvalue bounds for independent sets, J. Combin. Theory Ser. B, in press · Zbl 1156.05041
[6] Grone, R.; Merris, R., The Laplacian spectrum of a graph (II), SIAM J. Discrete Math., 7, 221-229 (1994) · Zbl 0795.05092
[7] Haemers, W. H., Interlacing eigenvalues and graphs, Linear Algebra Appl., 226-228, 593-616 (1995) · Zbl 0831.05044
[8] Mohar, B., Isoperimetric number of graphs, J. Combin. Theory Ser. B, 47, 274-291 (1989) · Zbl 0719.05042
[9] Mohar, B., The Laplacian spectrum of graphs, (Alavi, Y.; Chartrand, G.; Oellermann, O. R.; Schwenk, A. J., Graph Theory, Combinatorics, and Application (1991), Wiley: Wiley New York), 871-898 · Zbl 0840.05059
[10] Motzkin, T.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Turán, Canad. J. Math., 17, 533-540 (1965) · Zbl 0129.39902
[11] Rojo, O.; Soto, R.; Rojo, H., An always non-trivial upper bound for Laplacian graph eigenvalues, Linear Algebra Appl., 312, 155-159 (2000) · Zbl 0958.05088
[12] Wilf, H. S., Spectral bounds for the clique and independence numbers of graphs, J. Combin. Theory Ser. B, 40, 113-117 (1986) · Zbl 0598.05047
[13] Zhang, X. D.; Luo, R., The spectral radius of triangle-free graphs, Australas. J. Combin., 26, 33-39 (2002) · Zbl 1008.05089
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.