Laplacian matrix of a graph

Let $G$ be a finite graph with $n$ vectices and let $D$ be the incidence matrix (http://planetmath.org/ IncidenceMatrixWithRespectToAnOrientation) of $G$ with respect to some orientation. The Laplacian matrix of $G$ is defined to be $D{D}^T$.

If we let $A$ be the adjacency matrix of $G$ then it can be shown that $D{D}^T=\mathrm{\Delta }-A$, where $\mathrm{\Delta }=\text{diag}({\delta }_1,\mathrm{\dots },{\delta }_n)$ and ${\delta }_i$ is the degree of the vertex $v_i$. As a result, the Laplacian matrix is independent of what orientation is chosen for $G$.

The Laplacian matrix is usually denoted by $L(G)$. It is a positive semidefinite singular matrix, so that the smallest eigenvalue is 0.

Title	Laplacian matrix of a graph
Canonical name	LaplacianMatrixOfAGraph
Date of creation	2013-03-22 17:04:40
Last modified on	2013-03-22 17:04:40
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	8
Author	Mathprof (13753)
Entry type	Definition
Classification	msc 05C50
Defines	Laplacian matrix