TOPICS
Search

Laplacian Matrix


The Laplacian matrix, sometimes also called the admittance matrix (Cvetković et al. 1998, Babić et al. 2002) or Kirchhoff matrix, of a graph G, where G=(V,E) is an undirected, unweighted graph without graph loops (i,i) or multiple edges from one node to another, V is the vertex set, n=|V|, and E is the edge set, is an n×n symmetric matrix with one row and column for each node defined by

 L=D-A,
(1)

where D=diag(d_1,...,d_n) is the degree matrix, which is the diagonal matrix formed from the vertex degrees and A is the adjacency matrix. The diagonal elements l_(ij) of L are therefore equal the degree of vertex v_i and off-diagonal elements l_(ij) are -1 if vertex v_i is adjacent to v_j and 0 otherwise.

The Laplacian matrix of a graph is implemented in the Wolfram Language as KirchhoffMatrix[g].

A normalized version of the Laplacian matrix, denoted L, is similarly defined by

 L_(ij)(G)={1   if i=j and d_j!=0; -1/(sqrt(d_id_j))   if i and j are adjacent; 0   otherwise
(2)

(Chung 1997, p. 2).

The Laplacian matrix is a discrete analog of the Laplacian operator in multivariable calculus and serves a similar purpose by measuring to what extent a graph differs at one vertex from its values at nearby vertices. The Laplacian matrix arises in the analysis of random walks and electrical networks on graphs (Doyle and Snell 1984), and in particular in the computation of resistance distances. The Laplacian also appears in the matrix tree theorem.


See also

Algebraic Connectivity, Fiedler Vector, Laplacian Polynomial, Laplacian Spectral Radius, Laplacian Spectral Ratio, Matrix Tree Theorem, Resistance Distance, Spectral Graph Partitioning

Explore with Wolfram|Alpha

References

Akban, S. and Oboudi, M. R. "On the Edge Cover Polynomial of a Graph." Europ. J. Combin. 34, 297-321, 2013.Babić, D.; Klein, D. J.; Lukovits, I.; Nikolić, S.; and Trinajstić, N. "Resistance-Distance Matrix: A Computational Algorithm and Its Applications." Int. J. Quant. Chem. 90, 166-176, 2002.Bendito, E.; Carmona, A.; and Encinas, A. M. "Shortest Paths in Distance-Regular Graphs." Europ. J. Combin. 21, 153-166, 2000.Chung, F. R. K. Spectral Graph Theory. Providence, RI: Amer. Math. Soc., 1997.Cvetković, D. M.; Doob, M.; and Sachs, H. Spectra of Graphs: Theory and Applications, 3rd rev. enl. ed. New York: Wiley, 1998.Demmel, J. "CS 267: Notes for Lecture 23, April 9, 1999. Graph Partitioning, Part 2." http://www.cs.berkeley.edu/~demmel/cs267/lecture20/lecture20.html.Devillers, J. and Balaban, A. T. (Eds.). Topological Indices and Related Descriptors in QSAR and QSPR. Amsterdam, Netherlands: Gordon and Breach, pp. 74-75, 2000.Doyle, P. G. and Snell, L. Random Walks and Electric Networks. Washington, DC: Math. Assoc. Amer., 1984.Lin, Z.; Wang, J.; and Cai, M. "The Laplacian Spectral Ratio of Connected Graphs." 21 Feb 2023. https://arxiv.org/abs/2302.10491v1.Mohar, B. "The Laplacian Spectrum of Graphs." In Graph Theory, Combinatorics, and Applications, Vol. 2: Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988 (Ed. Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk). New York: Wiley, pp. 871-898, 1991.

Referenced on Wolfram|Alpha

Laplacian Matrix

Cite this as:

Weisstein, Eric W. "Laplacian Matrix." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LaplacianMatrix.html

Subject classifications