Let be a graph with vertices . The degree of vertex is denoted . Let be the Laplacian matrix of , so that , is when the vertices are adjacent, and is otherwise. The eigenvalues of are written as .

The graph is regular if all vertices have the same degree: . How can this property be seen from its Laplacian eigenvalues ?

Since the sum of eigenvalues is equal to the trace, we have . Moreover, is the trace of , which is equal to the sum of the squares of all entries of . This sum is because the th row of contains one entry equal to and entries equal to . In conclusion, .

The Cauchy-Schwarz inequality says that with equality if and only if all numbers are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference

is always nonnegative, and is equal to zero precisely when the graph is regular. This is how one can see the regularity of a graph from its Laplacian spectrum.

As an aside, is an even integer. Indeed, the sum is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that is even for every positive integer .

Up to a constant factor, is simply the degree variance: the variance of the sequence . What graph maximizes it for a given ? We want to have some very large degrees and some very small ones.

Let be the union of the complete graph on vertices and isolated vertices. The sum of degrees is and the sum of squares of degrees is . Hence,

For the maximum is attained by , that is there is one isolated vertex. For the maximum is . In general it is attained by .

The graph is disconnected. But any graph has the same degree variance as its complement. And the complement is always connected: it consists of a “center”, a complete graph on vertices, and “periphery”, a set of vertices that are connected to each central vertex. Put another way, is obtained from the complete bipartite graph by connecting all vertices of the group together.

Tom A. B. Snijders (1981) proved that and are the only graphs maximizing the degree variance; in particular, is the unique maximizer among the connected graphs. It is pictured below for .

This is a collection of entirely unoriginal remarks about Laplacian spectrum of graphs. For an accessible overview of the subject I recommend the M.S. thesis The Laplacian Spectrum of Graphs by Michael William Newman. It also includes a large table of graphs with their spectra. Here I will avoid introducing matrices and enumerating vertices.

Let be the vertex set of a graph. Write if are adjacent vertices. Given a function , define .
This is a linear operator (the graph Laplacian) on the Euclidean space of all functions with the norm . It is symmetric: and positive semidefinite: . Since equality is attained for constant , 0 is always an eigenvalue of .

This is the standard setup, but I prefer to change things a little and replace by the smaller space of functions with zero mean: . Indeed, maps to anyway, and since it kills the constants, it makes sense to focus on . It is a vector space of dimension where .

One advantage is that the smallest eigenvalue is 0 if and only if the graph is disconnected: indeed, is equivalent to being constant on each connected component. We also gain better symmetry between and the Laplacian of the graph complement, denoted . Indeed, since , it follows that for every . So, the identity holds on (it does not hold on ). Hence the eigenvalues of are obtained by subtracting the eigenvalues of from . As a corollary, the largest eigenvalue of is at most , with equality if and only if the graph complement is disconnected. More precisely, the multiplicity of eigenvalue is one less than the number of connected components of the graph complement.

Let denote the diameter of the graph. Then the number of distinct Laplacian eigenvalues is at least . Indeed, let be two vertices at distance from each other. Define and elsewhere. Also let for . Note that for all . One can prove by induction that when the distance from to is greater than , and when the distance from to is equal to . In particular, when and . This shows that is not a linear combination of . Since , it follows that is not a linear combination of . Hence the minimal polynomial of has degree at least , which implies the claim.

Let’s consider a few examples of connected graphs.

3 vertices

There are two connected graphs: the 3-path (D=2) and the 3-cycle (D=1). In both cases we get D distinct eigenvalues. The spectra are [1, 3] and [3, 3], respectively.

4 vertices

One graph of diameter 3, the path. Its spectrum is .

One graph of diameter 1, the complete graph. Its spectrum is . This pattern continues for other complete graphs: since the complement is the empty graph ( components), all eigenvalues are equal to .

Four graphs of diameter 2, which are shown below, with each caption being the spectrum.

Remarks:

The graph [1, 3, 4] has more distinct eigenvalues than its diameter.

The graph [2, 2, 4] is regular (all vertices have the same degree).

The smallest eigenvalue of graphs [1, 1, 4] and [2, 2, 4] is multiple, due to the graphs having a large group of automorphisms (here rotations); applying some of these automorphisms to an eigenfunctions for the smallest eigenvalue yields another eigenfunction.

[1, 3, 4] and [2, 4, 4] also have automorphisms, but their automorphisms preserve the eigenfunction for the lowest eigenvalue, up to a constant factor.

5 vertices

One graph of diameter 4, the path. Its spectrum is related to the golden ratio: it consists of .

One graph of diameter 1, the complete one: [5, 5, 5, 5]

Five graphs of diameter 3. All have connected complement, with the highest eigenvalue strictly between 4 and 5. None are regular. Each has 4 distinct eigenvalues.

14 graphs of diameter 2. Some of these are noted below.

Two have connected complement, so their eigenvalues are less than 5 (spectrum shown on hover):

1.382, 1.382, 3.618, 3.618

1.382, 2.382, 3.618, 4.618

One has both integers and non-integers in its spectrum, the smallest such graph. Its eigenvalues are .

Two have eigenvalues of multiplicity 3, indicating a high degree of symmetry (spectrum shown on hover).

1, 1, 1, 5

3, 5, 5, 5

Two have all eigenvalues integer and distinct:

1, 2, 4, 5

2, 3, 4, 5

The 5-cycle and the complete graph are the only regular graphs on 5 vertices.

6 vertices

This is where we first encounter isospectral graphs: the Laplacian spectrum cannot tell them apart.

Both of these have spectrum but they are obviously non-isomorphic (consider the vertex degrees):

Both have these have spectrum and are non-isomorphic.

Indeed, the second pair is obtained from the first by taking graph complement.

Also notable are regular graphs on 6 vertices, all of which have integer spectrum.

Here [3, 3, 3, 3, 6] (complete bipartite) and [2, 3, 3, 5, 5] (prism) are both regular of degree 3, but the spectrum allows us to tell them apart.

The prism is the smallest regular graph for which the first eigenvalue is a simple one. It has plenty of automorphisms, but the relevant eigenfunction (1 on one face of the prism, -1 on the other face) is compatible with all of them.

7 vertices

There are four regular graphs on 7 vertices. Two of them are by now familiar: 7-cycle and complete graph. Here are the other two, both regular of degree 4 but with different spectra.

There are lots of isospectral pairs of graphs on 7 vertices, so I will list only the isospectral triples, of which there are five.

Spectrum 0.676596, 2, 3, 3.642074, 5, 5.681331:

Spectrum 0.726927, 2, 3.140435, 4, 4, 6.132637:

Spectrum 0.867363, 3, 3, 3.859565, 5, 6.273073:

Spectrum 1.318669, 2, 3.357926, 4, 5, 6.323404:

All of the triples mentioned so far have connected complement: for example, taking the complement of the triple with the spectrum [0.676596, 2, 3, 3.642074, 5, 5.681331] turns it into the triple with the spectrum [1.318669, 2, 3.357926, 4, 5, 6.323404].

Last but not least, an isospectral triple with an integer spectrum: 3, 4, 4, 6, 6, 7. This one has no counterpart since the complement of each of these graphs is disconnected.

8 vertices

Regular graphs, excluding the cycle (spectrum 0.585786, 0.585786, 2, 2, 3.414214, 3.414214, 4) and the complete one.

When plotting the familiar elementary functions like x^{2} or exp(x), we only see whatever part of the infinitely long curve fits in the plot window. What if we could see the entire curve at once?

The double-tanh scale can help with that. The function u = tanh(x) is a diffeomorphism of the real line onto the interval (-1, 1). Its inverse, arctanh or artanh or arth or or , whatever you prefer to call it, does the opposite. So, conjugating any function by the hyperbolic tangent produces a function which we can plot in its entirety. Let’s try this.

Out of linear functions y = kx, only y=x and y=-x remain lines.

The powers of x, from 1 to 4, look mostly familiar:

Sine, cosine, and tangent functions are not periodic anymore:

The exponential function looks concave instead of convex, although I don’t recommend trying to prove this by taking the second derivative of its tanh-conjugate.

The Gaussian loses its bell-shaped appearance and becomes suspiciously similar to a semicircle.

This raises the question: which function does appear as a perfect semi-circle of radius 1 on the tanh-tanh scale? Turns out, it is . Here it is shown in the normal coordinate system.

Graphs are often encoded by their adjacency matrix: a symmetric matrix where in the entry means there is an edge between vertices labeled and . Another useful encoding is the incidence matrix, in which rows correspond to edges and columns to vertices (or the other way around). Having in the entry means that th edge is incident to th vertex. Simply put, each row contains exactly two nonzero entries, which indicate the endpoints of an edge.

An incidence matrix is generally rectangular. It is the square matrix when the graph has as many edges as vertices. For example, the 4-cycle has incidence matrix

(up to relabeling of vertices). This matrix is not invertible. Indeed, , which is a reflection of the fact that the graph is bipartite. Indeed, for any bipartite graph the vector describing a 2-coloring of the vertices belongs to the kernel of the incidence matrix.

The incidence matrix of an odd cycle is invertible, however. What other such “invertible” graphs exist? Clearly, the disjoint union of “invertible” graphs is itself invertible, so we can focus on connected graphs.

There are no invertible graphs on 1 or 2 vertices. For 3 through 8 vertices, exhaustive search yields the following counts:

1 graph on 3 vertices (3-cycle)

1 graph on 4 vertices (3-cycle with an edge attached)

4 graphs on 5 vertices

8 graphs on 6 vertices

23 graphs on 7 vertices

55 graphs on 8 vertices

The numbers match the OEIS sequence A181688 but it’s not clear whether this is for real or a coincidence. The brute force search takes long for more than 8 vertices. It’s probably better to count such graphs by using their (folklore?) characterization as “trees planted on an odd cycle”, described by Chris Godsil on MathOverflow.

Some examples:

The examples were found and plotted by this Python script.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from itertools import combinations
def is_invertible(graph, n):
matrix = []
for i in range(n):
row = [0]*n
row[graph[i][0]] = 1
row[graph[i][1]] = 1
matrix.append(row)
return abs(np.linalg.det(matrix)) > 0.5
n = 6 # number of vertices
graphs = combinations(combinations(range(n), 2), n)
inv = []
for g in graphs:
if is_invertible(g, n):
gr = nx.Graph(g)
if nx.is_connected(gr) and not any([nx.is_isomorphic(gr, gr2) for gr2 in inv]):
inv.append(gr)
nx.draw_networkx(gr)
plt.savefig("graph{}_{}.png".format(n, len(inv)))
plt.clf()
print("There are {} connected invertible graphs with {} vertices".format(len(inv), n))

I wanted some random examples of graphs where every vertex has degree between two given parameters, minDegree and maxDegree. Like this one:

The approach I took was very simple (and not suitable for construction of very large or very regular graphs). Each edge appears with probability p. If the minimal degree is too small, this probability is multiplied by 1.1. If the maximal degree is too big, the probability is divided by 1.1. Either way, the process repeats until success.

So far, this blog had too much Matlab/Scilab and not enough Python. I’ll try to restore the balance. Here, numpy generates random matrices and takes care of degree restrictions; networkx lays out the graph.

import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
vertices = 15
minDegree = 3
maxDegree = 4
p = 0.5
success = False
while not success:
a = (np.random.random((vertices, vertices)) < p).astype(int)
a = np.maximum(a, np.matrix.transpose(a))
np.fill_diagonal(a, 0)
s = a.sum(axis=1)
success = True
if min(s) < minDegree:
success = False
p = p * 1.1
if max(s) > maxDegree:
success = False
p = p / 1.1
g = nx.Graph(a)
nx.draw_networkx(g)
plt.show()