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 ni-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 = A - 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 = A + 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/ad_id_j

where d_i and d_j 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