# 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 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):

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).

Two have all eigenvalues integer and distinct:

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.

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.

#### Degree 6 regular

Credits: the list of graphs by Brendan McKay and NetworkX library specifically the methods read_graph6 (to read the files provided by Prof. McKay), laplacian_spectrum, diameter, degree, and draw.

This site uses Akismet to reduce spam. Learn how your comment data is processed.