Laplacian matrix

Definition

Suppose $G$ is a finite undirected graph. Let $n$ be the size of the vertex set $V(G)$. Fix a bijective correspondence $v:\{1,2,\dots ,n\}\to V(G)$. The Laplacian matrix of $G$ is a $n\times n$ matrix defined in the following equivalent ways:

1. It is the matrix difference $D-A$ where $D$ is the degree matrix of $G$ and $A$ is the adjacency matrix of $G$, both for the same vertex mapping $v$.
2. It is the product $M^{T}M$ where $M$ is an oriented incidence matrix of $G$ (where the vertices are ordered by the function $v$) and $M^{T}$ is the matrix transpose of $M$.

Properties

The Laplacian matrix is a diagonally dominant matrix.