×

The Laplacian spectrum of a graph. (English) Zbl 1058.05048

Summary: Let \(G = (V, E)\) be a simple graph. Denote by \(D(G)\) the diagonal matrix of its vertex degrees and by \(A(G)\) its adjacency matrix. Then, the Laplacian matrix of \(G\) is \(L(G) = D(G) - A(G)\). The first and second section of this paper contain an introduction and some known results, respectively. The third section is devoted to properties of the Laplacian spectrum. The fourth section contains a characterization of graphs. The fifth section relates the Laplacian eigenvalues with the graph structure.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cvetković, D. M.; Doob, M.; Sachs, H., Spectra of Graphs, Theory and Application (1980), Academic Press: Academic Press New York · Zbl 0458.05042
[2] Merris, R., Laplacian matrices of fraphs: A survey, Linear Algebra Appl., 197-198, 143-176 (1994) · Zbl 0802.05053
[3] Mohar, B., The Laplacian spectrum of graphs, in graph theory, combinatorics, and applications, (Alavi, Y.; Chartrand, G.; Oellermann, O. R.; Schwenk, A. J., Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs. Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs, Western Michigan University, Kalamazoo, 1988 (1991), Wiley: Wiley New York), 871-898 · Zbl 0840.05059
[4] Grone, R.; Merris, R., The Laplacian Spectrum of a Graph \(II^*\), SIAM J. Discrete Math., 7, 2, 221-229 (1994) · Zbl 0795.05092
[5] Heuvel, J. V.D., Hamilton cycles and eigenvalues of graphs, Linear Algebra Appl., 226-228, 723-730 (1995) · Zbl 0846.05059
[6] Guo, J.-M., On the Laplacian spectral radius of a tree, Linear Algebra Appl., 368, 379-385 (2003) · Zbl 1036.05030
[7] So, W., Rank one perturbation and its application to the Laplacian spectrum of a graph, Linear and Multilinear Algebra, 46, 193-198 (1999) · Zbl 0935.05065
[8] Das, K. C., Sharp lower bounds on the Laplacian eigenvalues of trees, Linear Algebra Appl., 384, 155-169 (2004) · Zbl 1047.05027
[9] Das, K. C., A characterization on graphs which achieve the upper bound for the largest Laplacian eigenvalue of graphs, Linear Algebra Appl., 376, 173-186 (2004) · Zbl 1042.05059
[10] K.C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Mathematics; K.C. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Mathematics · Zbl 1051.05033
[11] Grone, R.; Zimmermann, G., Large eigenvalues of the Laplacian, Linear and Multilinear Algebra, 28, 45-47 (1990) · Zbl 0714.05039
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.