## You are here

HomeLaplacian matrix of a graph

## Primary tabs

# Laplacian matrix of a graph

Let $G$ be a finite graph with $n$ vectices and let $D$ be the incidence matrix 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.

Defines:

Laplacian matrix

Type of Math Object:

Definition

Major Section:

Reference

## Mathematics Subject Classification

05C50*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections