Laplacian matrices of graphs: A survey (Q1319985)

Let \(A(G)\) be the adjacency matrix and \(D(G)\) the diagonal matrix of vertex degrees of a graph \(G\). The matrix \(L(G)= D(G)- A(G)\) is called the Laplacian (matrix) of \(G\). The matrix \(L(G)\) is also known as the admittance matrix or the Kirchhoff matrix of \(G\). The name Laplacian is fully justified by the fact that \(L(G)\) is a discrete analog of the Laplacian operator from calculus. \(L(G)\) is a positive semi-definite matrix and its second smallest eigenvalue is called the algebraic connectivity of \(G\), as introduced by \textit{M. Fiedler} [Czech. Math. J. 23, 298-305 (1973; Zbl 0265.05119)]. By the well-known matrix tree theorem, \(L(G)\) is related to the number of spanning trees of \(G\). During the last ten years the eigenvalues of \(L(G)\) have been intensively studied including their applications in chemistry and physics. The paper under review is a well-written expository paper on graph Laplacians. The section titles read: 1. Introduction, 2. The spectrum, 3. The algebraic connectivity, 4. Congruence and equivalence, 5. Chemical applications, 6. Immanants. There are 155 references. An expository sequel to this paper, which is written by the same author, is going to appear in Linear and Multilinear Algebra. There is also a good review on graph Laplacians by \textit{B. Mohar} [Discrete Math. 109, No. 1-3, 171-183 (1992; Zbl 0783.05073)].