Laplacian matrix of a graph

Let G be a finite graph with n vectices and let D be the incidence matrixMathworldPlanetmath ( IncidenceMatrixWithRespectToAnOrientation) of G with respect to some orientation. The Laplacian matrix of G is defined to be DDT.

If we let A be the adjacency matrixMathworldPlanetmath of G then it can be shown that DDT=Δ-A, where Δ=diag(δ1,,δn) and δi is the degree of the vertex vi. 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 semidefinitePlanetmathPlanetmath singular matrix, so that the smallest eigenvalueMathworldPlanetmathPlanetmathPlanetmathPlanetmath 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