The Laplacian matrix, sometimes also called the admittance matrix (Cvetković et al. 1998, Babić et al. 2002) or Kirchhoff matrix, of a graph, where is an undirected,
unweighted graph without graph loops or multiple edges from
one node to another,
is the vertex set, , and is the edge set, is an symmetric matrix
with one row and column for each node defined by
(1)
where
is the degree matrix, which is the diagonal
matrix formed from the vertex degrees and is the adjacency
matrix. The diagonal elements of are therefore equal the degree of vertex and off-diagonal elements are if vertex is adjacent to and 0 otherwise.
A normalized version of the Laplacian matrix, denoted , is similarly defined by
(2)
(Chung 1997, p. 2).
The Laplacian matrix is a discrete analog of the Laplacian operator in multivariable calculus. For a real-valued function on the vertex
set,
is the sum of over the vertices
adjacent to .
Thus
is a discrete harmonic function at a
graph vertex of positive vertex
degreeiff the corresponding component of is zero. 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.
, where 
is an undirected,
unweighted graph without graph loops 
or multiple edges from
one node to another, 
is the vertex set, 
, and 
is the edge set, is an 
symmetric matrix
with one row and column for each node defined by
is the degree matrix, which is the diagonal
matrix formed from the vertex degrees and 
is the adjacency
matrix. The diagonal elements 
of 
are therefore equal the degree of vertex 
and off-diagonal elements 
are 
if vertex 
is adjacent to 
and 0 otherwise.
, is similarly defined by
on the vertex
set, 
is the sum of 
over the vertices
adjacent to 
.
Thus 
is a discrete harmonic function at a
graph vertex of positive vertex
degree iff the corresponding component of 
is zero. 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.
