# 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 $DD^{T}$.

If we let $A$ be the adjacency matrix of $G$ then it can be shown that $DD^{T}=\Delta-A$, where $\Delta=\textrm{diag}(\delta_{1},\ldots,\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 LaplacianMatrixOfAGraph 2013-03-22 17:04:40 2013-03-22 17:04:40 Mathprof (13753) Mathprof (13753) 8 Mathprof (13753) Definition msc 05C50 Laplacian matrix