# 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 |