zbMATH — the first resource for mathematics

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\).

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
Full Text: DOI
[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 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 · 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, (), 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. 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.