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.


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


[1] Cvetković, D.M.; Doob, M.; Sachs, H., Spectra of graphs, theory and application, (1980), 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, (), 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 (to appear). · 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. 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.