Laplacian spectrum of small graphs

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 ${V}$ be the vertex set of a graph. Write ${u\sim v}$ if ${u, v}$ are adjacent vertices. Given a function ${f\colon V\to \mathbb R}$ , define ${L f(v) = \sum_{u\colon u\sim v}(f(v)-f(u))}$ .
This is a linear operator (the graph Laplacian) on the Euclidean space ${\ell^2(V)}$ of all functions ${f\colon V\to \mathbb R}$ with the norm ${\|f\|^2 = \sum_{v\in V} f(v)^2}$ . It is symmetric: ${\langle L f, g\rangle = \langle f, L g\rangle }$ and positive semidefinite: ${\langle L f, f\rangle = \frac12 \sum_{u\sim v}(f(u)-f(v))^2\ge 0}$ . Since equality is attained for constant ${f}$ , 0 is always an eigenvalue of ${L}$ .

This is the standard setup, but I prefer to change things a little and replace ${\ell^2(V)}$ by the smaller space ${\ell^2_0(V)}$ of functions with zero mean: ${\sum_{v\in V}f(v)=0}$ . Indeed, ${L}$ maps ${\ell^2(V)}$ to ${\ell^2_0(V)}$ anyway, and since it kills the constants, it makes sense to focus on ${\ell^2_0(V)}$ . It is a vector space of dimension ${n-1}$ where ${n=|V|}$ .

One advantage is that the smallest eigenvalue is 0 if and only if the graph is disconnected: indeed, ${\langle L f, f\rangle=0}$ is equivalent to ${f}$ being constant on each connected component. We also gain better symmetry between ${L}$ and the Laplacian of the graph complement, denoted ${L'}$ . Indeed, since ${L' f(v) = \sum_{u\colon u\not \sim v}(f(v)-f(u))}$ , it follows that ${(L+L')f(v) = \sum_{u\colon u\ne v} (f(v)-f(u)) = n f(v)}$ for every ${f\in \ell^2_0(V)}$ . So, the identity ${L+L' = nI}$ holds on ${\ell^2_0(V)}$ (it does not hold on ${\ell^2(V)}$ ). Hence the eigenvalues of ${L'}$ are obtained by subtracting the eigenvalues of ${L}$ from ${n}$ . As a corollary, the largest eigenvalue of ${L}$ is at most ${n}$ , with equality if and only if the graph complement is disconnected. More precisely, the multiplicity of eigenvalue ${n}$ is one less than the number of connected components of the graph complement.

Let ${D}$ denote the diameter of the graph. Then the number of distinct Laplacian eigenvalues is at least ${D}$ . Indeed, let ${u, v}$ be two vertices at distance ${D}$ from each other. Define ${f_0(u) = 1}$ and ${f_0=0}$ elsewhere. Also let ${f_k=L^k f_0}$ for ${k=1, 2, \dots}$ . Note that ${f_k\in \ell_0^2(V)}$ for all ${k\ge 1}$ . One can prove by induction that ${f_k(w)=0}$ when the distance from ${w}$ to ${u}$ is greater than ${k}$ , and ${(-1)^k f_k(w) > 0}$ when the distance from ${w}$ to ${u}$ is equal to ${k}$ . In particular, ${f_k(v) = 0}$ when ${k<D}$ and ${f_D(v)\ne 0}$ . This shows that ${f_D}$ is not a linear combination of ${f_1, \dots, f_{D-1}}$ . Since ${f_k = L^{k-1}f_1}$ , it follows that ${L^{D-1}}$ is not a linear combination of ${L^0, L^1, \dots, L^{D-2}}$ . Hence the minimal polynomial of ${L}$ has degree at least ${D}$ , 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 ${[2-\sqrt{2}, 2, 2+\sqrt{2}]}$ .
One graph of diameter 1, the complete graph. Its spectrum is ${[4, 4, 4]}$ . This pattern continues for other complete graphs: since the complement is the empty graph ( ${n}$ components), all ${n-1}$ eigenvalues are equal to ${n}$ .
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 ${(3\pm \sqrt{5})/2, (5\pm \sqrt{5})/2}$ .
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 ${3\pm \sqrt{2}, 3, 5}$ .

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 ${3\pm \sqrt{5}, 2, 3, 3}$ but they are obviously non-isomorphic (consider the vertex degrees):

Both have these have spectrum ${3\pm \sqrt{5}, 3, 3, 4}$ 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.

7-832 — 3.198, 3.198, 4.555, 4.555, 6.247, 6.247

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.