# Graph Laplacian and other matrices associated with a graph

There are several ways to associate a matrix with a graph. The properties of these matrices, especially spectral properties (eigenvalues and eigenvectors) tell us things about the structure of the corresponding graph. This post is a brief reference for keeping these various matrices straight.

The most basic matrix associated with a graph is its adjacency matrix, denoted A. For a graph with n nodes, create an n×n matrix filled with zeros, then fill in a 1 in the ith row and jth column if there is an edge between the ith and jth node.

Next let D be the diagonal matrix whose ith element is the degree of the ith node, i.e. the number of edges attached to the ith node. The Laplacian matrix of the graph is

L– D.

The Laplacian matrix of a graph is analogous to the Laplacian operator in partial differential equations. It is sometimes called the Kirchhoff matrix or the admittance matrix.

The signless Lapacian matrix is

Q = D.

There are connections between the signless Laplacian and bipartite components. For example, the multiplicity of 0 as an eigenvalue of Q equals the number of bipartite components in the graph.

There are other variations of the Laplacian matrix. The normalized Laplacian matrix has 1’s down the diagonal. If there is an edge between the ith and jth nodes, the ij entry is

-1/√didj

where di and dj are the degrees of the ith and jth nodes. If there is no edge between the ith and jth nodes, the ij entry is 0.

The distance matrix of a graph is the matrix D whose ijth entry is the distance from the ith node to the jth node. (Sorry, this D is different than the one above. Books often write this as a script D, something I can’t do in plain HTML.) The transmission of a node v, Tr(v), is the sum of the distances from v to every element connected to v. The distance Laplacian of a graph is Diag(Tr) – D where Diag(Tr) is the diagonal matrix whose ith entry is the transmission of the ith node and D here is the distance matrix. The signless distance Laplacian of a graph is Diag(Tr) + D.

Reference: Inequalities for Graph Eigenvalues

Related posts:

## 16 thoughts on “Graph Laplacian and other matrices associated with a graph”

1. The wonders of Unicode let you use both D and . I would hope it’s safe to assume adequate font coverage in this world of 2015.

2. Ha ha. I saw the math bold script D (U+1D4D3) in the comment entry box, but it’s gone now that the comment has been posted.

2015 indeed 🙁

3. Marius: Unfortunately Unicode support is indeed disappointing. I blogged a while back about which Unicode characters you can depend on and this list is pretty small, only a small portion of the Basic Multilingual Plane and nothing in the extended planes where things like U+1D4D3 live.

4. GlennF

“the multiplicity of 0 as an eigenvalue of Q equals the number of bipartite components in the graph”
Does this just mean the nullity of Q is equal to the number of bipartite components of the graph, or an I misreading this?

5. JDS Purohit

Using MathJax, you can use AMSTex fonts.

6. Yes and no. MathJax will automate creating an image file from LaTeX and inserting it into your HTML, but it looks like a foreign symbol pasted into the text. That’s OK, and maybe that would be better than what I did, but it’s not great. I like to use LaTeX for displayed equations if necessary, but not in the middle of a paragraph.

7. Shevach Riabtsev

In most cases adjacency matrices are sparse and there are a lot of techniques to manipulate (multiply or store) sparse matrices.

There is a method to know whether a given graph is connected (i.e. any two vertexes can achievable).
Let A is adjacency matrix of the graph. if the matrix B = I+A+A^2+.. +A^n has zero entries the the graph is disconnected and vice versa

8. Rob Doherty

Great post!