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 *i*th row and *j*th column if there is an edge between the *i*th and *j*th node.

Next let *D* be the diagonal matrix whose *i*th element is the degree of the *i*th node, i.e. the number of edges attached to the *i*th 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 *i*th and *j*th nodes, the *ij* entry is

-1/√*d*_{i}*d*_{j}

where *d*_{i} and *d*_{j} are the degrees of the *i*th and *j*th nodes. If there is no edge between the *i*th and *j*th nodes, the *ij* entry is 0.

The **distance matrix** of a graph is the matrix *D* whose *ij*th entry is the distance from the *i*th node to the *j*th 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 *i*th entry is the transmission of the *i*th 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**: