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 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.
, 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
