graph – Calculus VII

Graphs with integer normalized Laplacian eigenvalues

Let ${V}$ be the vertex set of a graph; all graphs here are assumed connected. Write ${u\sim v}$ if ${u, v}$ are adjacent vertices. The Laplacian of a function ${f\colon V\to \mathbb R}$ is defined as ${L f(v) = \sum_{u\colon u\sim v}(f(v)-f(u))}$ . Its properties were discussed earlier in Laplacian spectrum of small graphs.

The normalized Laplacian involves the vertex degree ${d_v}$ (the number of vertices adjacent to ${v}$ ). It is defined by

$L_N f(v) = \frac{1}{\sqrt{d_v}}\sum_{u\colon u\sim v}\left( \frac{f(v)}{\sqrt{d_v}} - \frac{f(u)}{\sqrt{d_u}} \right)$

The matrix of ${L_N}$ is obtained by multiplying the matrix of ${L}$ on both sides by the diagonal matrix with ${1/\sqrt{d_v}}$ on the diagonal. Hence, ${L_N}$ is also positive semidefinite and has the same rank as ${L}$ . In particular, it has a simple eigenvalue 0 and the rest of eigenvalues are positive. Let us write ${\mu_1 \le \cdots \le \mu_n}$ for the eigenvalues of ${L_N}$ . In this notation, ${\mu_1= 0}$ and ${\mu_k>0}$ for ${k\ge 2}$ .

There are many graphs with integer Laplacian eigenvalues; they do not seem to follow any particular pattern. In contrast, the graphs with integer normalized Laplacian eigenvalues have a simple description.

The matrix of normalized Laplacian ${L_N}$ has ${1}$ in every diagonal entry. Its off-diagonal entries are ${-1/\sqrt{d_ud_v}}$ if ${u\sim v}$ , and ${0}$ otherwise. Since the trace is ${n}$ , and there are ${n-1}$ positive eigenvalues, the way that a normalized Laplacian spectrum can consist of integers is ${(0, 1, \ldots, 1, 2)}$ .

It turns out that the largest normalized Laplacian eigenvalue ${\mu_n}$ equal to ${2}$ if and only if the graph is bipartite; otherwise it is less than ${2}$ (as a reminder, all graphs are assumed connected in this post). Indeed, ${\mu_n}$ is the norm of ${L_N}$ , which is the supremum of ${\langle L_N f, f\rangle/ \langle f, f\rangle}$ over all functions ${f}$ . A computation shows ${\langle L_N f, f\rangle = \sum_E (f(u)/\sqrt{d_u} - f(v) / \sqrt{d_v})^2}$ where the sum is taken over the edge set ${E}$ : each edge contributes one term to the sum, with ${u, v}$ being its endpoints. The sum becomes simpler if we write ${f(v)=\sqrt{d_v} g(v)}$ ; after this substitution,

$\mu_n = \sup_g \frac{\sum_E (g(u)-g(v))^2 }{\sum_V g(v)^2 d_v}$

The denominator can be rewritten as a sum over edges, namely ${\sum_E (g(u)^2 + g(v)^2) }$ . This shows that the introduction of vertex degree into the denominator achieves certain symmetry: each value of ${f}$ appears in the numerator as many times as in the denominator.

Since ${(g(u)-g(v))^2 \le 2(g(u)^2 + g(v)^2)}$ , the numerator is at most ${2 \sum_E (g(u)^2 + g(v)^2)}$ . Thus ${\mu_n\le 2}$ , and to achieve equality here we need ${g(u) + g(v) = 0}$ whenever ${u\sim v}$ . This requires ${|g|}$ to be constant and the graph to be bipartite, its 2-coloring provided by ${\mathrm{sign}\,g}$ . Conversely, any 2-coloring of a graph provides us with a function ${g\colon V\to \{-1, 1\}}$ for which ${\sum_E (g(u)-g(v))^2 = 2\sum_V g(v)^2 d_v}$ according to the above.

To achieve integer spectrum, we also need ${1}$ to be an eigenvalue of multiplicity ${n-2}$ for ${L_N}$ , which is equivalent to ${\mathrm{rank}\,(I-L_N) = 2}$ . Since the graph is bipartite, ${I-L_N}$ has the block form

$I - L_N = \begin{pmatrix} 0 & A \\ A^t & 0\end{pmatrix}$

where the (possibly rectangular) block ${A}$ has entries ${1/\sqrt{d_u d_v}}$ corresponding to ${u\sim v}$ . In order for ${I-L_N}$ to have rank 2, the matrix ${A}$ must have rank 1. Any zero entry of a rank-1 matrix lies in a zero row, but ${A}$ cannot have a zero row because the graph is connected. Thus, all entries of ${A}$ are positive, which means we have a complete bipartite graph.

The converse is immediate: for a complete bipartite graph ${K_{p, q}}$ the matrix ${A}$ has all entries equal to ${1/\sqrt{pq}}$ , hence its rank is 1.

As a final remark, the ordinary (un-normalized) Laplacian of a complete bipartite graph ${K_{p, q}}$ also has integer eigenvalues. Indeed, the complement of ${K_{p, q}}$ is the disjoint union of complete graphs ${K_p}$ and ${K_q}$ , with the spectra ${(0, p, \ldots, p)}$ and ${(0, q, \ldots, q)}$ . Passing to the complement means replacing each eigenvalue ${\lambda}$ by ${n-\lambda}$ , except that one ${0}$ stays ${0}$ (this is discussed in Laplacian spectrum of small graphs). Hence, the Laplacian spectrum of ${K_{p, q}}$ consists of: simple eigenvalues ${0}$ and ${n}$ , eigenvalue ${p}$ of multiplicity ${q-1}$ , and eigenvalue ${q}$ of multiplicity ${p-1}$ . Worth noting that the Laplacian spectrum determines a complete bipartite graph up to an isomorphism, while the normalized Laplacian spectrum does not.

The effect of adding an edge on Laplacian eigenvalues

Adding an edge to a connected graph (between two of its existing vertices) makes the graph “even more” connected. How to quantify this? The Poincaré inequality gives a way to do this: for any function ${f\colon V\to \mathbb R}$ with zero mean,

$\sum_V f(v)^2 \le C \sum_E (f(u)-f(v))^2$

where the sum on the left is over the vertex set ${V}$ , the sum on the right is over the edge set ${E}$ , and ${u, v}$ on the right are the endpoints of an edge. Suppose ${C}$ is the smallest possible constant in this inequality, the Poincaré constant of the graph. Adding an edge to the graph does not change the sum on the left but may increase the sum on the right. Thus, the new Poincaré constant ${C'}$ satisfies ${C'\le C}$ : greater connectivity means smaller Poincaré constant.

It is more convenient to work with the reciprocal of ${C}$ , especially because ${1/C = \lambda_2}$ , the smallest positive eigenvalue of the graph Laplacian. Let ${\lambda_2'}$ be the corresponding eigenvalue after an edge is added. The above shows that ${\lambda_2 \le \lambda_2'}$ . But there is also an upper bound on how much this eigenvalue (or any Laplacian eigenvalue) can grow. Indeed, adding an edge amounts to adding the matrix

$B = \begin{pmatrix} 1 & -1 \\ -1 & 1 \end{pmatrix}$ (with a bunch of zero rows/columns)

to the Laplacian matrix ${L}$ . The eigenvalues of ${B}$ are ${0}$ and ${2}$ . As a consequence of the Courant-Fischer minimax formulas, the ordered eigenvalues ${\lambda_1 \le \dots \le \lambda_n}$ satisfy ${\lambda_k(L) \le \lambda_k(L+B) \le \lambda_k(L) + 2}$ for every ${k}$ .

Both of the above bounds are sharp. If an diagonal edge is added to the 4-cycle,

C4add

the smallest positive eigenvalue remains the same ( ${2}$ ). The reason is that a typical eigenfunction for ${\lambda_2}$ takes on values ${-1, 0, 1, 0}$ (in cyclic order) and adding an edge between two vertices with the same value of such eigenfunction does not affect the Poincaré constant.

On the other hand, adding one more edge increases ${\lambda_2}$ from ${2}$ to ${4}$ .

C4add2

Normalized Laplacian

Another form of the Poincaré inequality involves the vertex degree: when summing over vertices, we give each of them weight equal to the number of neighbors.

$\sum_V f(v)^2 d_v \le C \sum_E (f(u)-f(v))^2$ provided $\sum_V f(v)d_v = 0$

Here ${1/C = \mu_2}$ , the smallest positive eigenvalue of the normalized Laplacian ${L_N}$ , the matrix with ${1}$ on the diagonal, where off-diagonal entries are ${-1/\sqrt{d_ud_v}}$ if ${u\sim v}$ , and ${0}$ otherwise. The sum of the normalized Laplacian eigenvalues is equal to ${n}$ (the number of vertices), regardless of how many edges are there. So we cannot expect all them to grow when an edge is added. But how do they change?

Let ${\mu_2'}$ be the corresponding eigenvalue after an edge is added.
Here are two examples for which ${\mu_2' - \mu_2 = 1/2}$ :

Completing a 3-path to a 3-cycle increases the eigenvalue from 1 to 3/2.

P3add

Completing a 4-path to a 4-cycle increases the eigenvalue from 1/2 to 1.

P4add
This pattern does not continue: “5-path to 5-cycle” results in a smaller increase, which is not even largest among 5-vertex graphs. It appears that the above examples are the only two cases of ${\mu_2' - \mu_2 = 1/2}$ , with all other graphs having ${\mu_2' - \mu_2 < 1/2}$ . (I do not have a proof of this.)

The opposite direction

Adding an edge can also make ${\mu_2}$ smaller (thus, the weighted Poincaré constant becomes larger, showing that it may not be as useful for quantifying the connectivity of a graph). The smallest example is adding an edge to the star graph on 4 vertices:

S4add

here ${\mu_2 = 1}$ but ${\mu_2' = 5/4 - \sqrt{33}/12 \approx 0.77}$ .

Let us analyze the star graphs on ${n}$ vertices, for general ${n}$ . In an earlier post we saw that ${\mu_2 = 1}$ , so it remains to find ${\mu_2'}$ . Let us order the vertices so that ${1}$ is the center of the star and ${(2,3)}$ is the added edge. Write ${\beta = -1/\sqrt{n-1}}$ for brevity. Then the normalized Laplacian matrix ${L_N}$ is

$\begin{pmatrix} 1 & \beta/\sqrt{2} & \beta/\sqrt{2} & \beta & \cdots & \beta \\ \beta/\sqrt{2} & 1 & -1/2 & 0 & \cdots & 0 \\ \beta/\sqrt{2} & -1/2 & 1 & 0 & \cdots & 0 \\ \beta & 0 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \beta & 0 & 0 & 0 & \cdots & 1 \\ \end{pmatrix}$

where all rows numbered ${i > 3}$ consist of ${\beta}$ in the first column and ${1}$ in the ${i}$ th column. This shows that ${L_N-I}$ has rank ${4}$ , hence ${1}$ is an eigenvalue of multiplicity ${n-4}$ . Also, ${0}$ is a simple eigenvalue as for any connected graph. Less obviously, ${3/2}$ is an eigenvalue with the corresponding eigenvector ${(0, 1, -1, 0, \dots, 0)}$ – this eigenvalue comes from the submatrix in row/columns 2 and 3, where the surrounding values in these row/columns are nice enough to cancel out. We are left with two eigenvalues to find, and we know their sum is ${n - (n-4) - 3/2 = 5/2}$ . This means the characteristic polynomial of ${L_N}$ is of the form

$p(t) = t (t-1)^{n-4} (t-3/2) (t^2 - 5t/2 + \gamma)$

where the constant ${\gamma}$ remains to be found. I am going to skip to the answer here: ${\gamma = n/(n-1)}$ . The quadratic formula delivers the last two eigenvalues:

$\frac14 \left( 5 \pm \sqrt{\frac{9n-25}{n-1}}\right)$

The smaller of these is ${\mu_2'}$ that we were looking for:

$\mu_2' = \frac14 \left( 5 - \sqrt{\frac{9n-25}{n-1}}\right) \to \frac12$ as ${n\to\infty}$

Thus, adding an edge to a star graph results in negative ${\mu_2' - \mu_2}$ which decreases to ${-1/2}$ as ${n\to\infty}$ . Exhaustive search for ${n\le 9}$ shows that the star graph has the smallest value of ${\mu_2' - \mu_2}$ among all graphs on ${n}$ vertices. It is reasonable to expect this pattern to continue, which would imply ${\mu_2' - \mu_2 > -1/2}$ in all cases.

Maximal algebraic connectivity among graphs of bounded degree

The algebraic connectivity ${ a(G) }$ of a graph ${G }$ is its smallest nontrivial Laplacian eigenvalue. Equivalently, it is the minimum of edge sums ${\sum_{e\in E} df(e)^2}$ over all functions ${f\colon V\to\mathbb R}$ normalized by ${ \sum_{v\in V} f(v) = 0 }$ and ${\sum_{v\in V} f(v)^2 = 1 }$ . Here ${ V, E }$ are vertex/edge sets, and ${ df(e)}$ means the difference of the values of ${f }$ at the vertices of the edge ${ e}$ .

It is clear from the definition that adding edges to ${ G}$ cannot make ${a(G) }$ smaller; thus, among all graphs on ${n }$ vertices the maximal value of ${a(G) }$ is attained by the complete graph, for which ${a(G) = n}$ . For any other graph ${ a(G)\le n-2}$ which can be shown as follows. Pick two non-adjacent vertices ${u }$ and ${v }$ and let ${f(u)=1/\sqrt{2} }$ , ${ f(v) = -1/\sqrt{2}}$ , and ${f=0 }$ elsewhere. This function is normalized as required above, and its edge sum ${\sum_{e\in E} df(e)^2}$ is at most ${ n-2}$ since there are at most ${ 2(n-2)}$ edges with a nonzero contribution.

What if we require the graph to have degree vertex at most ${d}$ , and look for maximal connectivity then? First of all, only connected graphs are under consideration, since ${a(G)=0}$ for non-connected graphs. Also, only the cases ${n\ge d+2 }$ are of interest, otherwise the complete graph wins. The argument in the previous paragraph shows that ${ a(G) \le d}$ but is this bound attained?

The case ${d=2}$ is boring: the only two connected graphs are the path ${P_n}$ and the cycle ${ C_n}$ . The cycle wins with ${a(C_n) = 2(1-\cos(2\pi/n)) }$ versus ${ a(P_n) = 2(1-\cos(\pi/n))}$ .

When ${ d=4}$ , one might suspect a pattern based on the following winners:

nd6-4-108 — 6 vertices, max degree 4, with a = 4

nd7-4-832 — 7 vertices, max degree 4, with a = 3.2

The structure of these two is the same: place ${n }$ points on a circle, connect each of them to ${4 }$ nearest neighbors.

But this pattern does not continue: the 8-vertex winner is completely different.

nd8-4-4575a — 8 vertices, max degree 4, with a = 4

This is simply the complete bipartite graph ${ K_{4, 4} }$ . And it makes sense that the “4 neighbors” graph loses when the number of vertices is large: there is too much “redundancy” among its edges, many of which connect the vertices that were already connected by short paths.

In general, when ${n = 2d }$ , the complete bipartite graph ${ K_{d, d}}$ achieves ${a = d }$ and therefore maximizes the algebraic connectivity. The fact that ${a(K_{d, d}) = d }$ follows by considering graph complement, as discussed in Laplacian spectrum of small graphs. The complement of ${K_{d, d} }$ is the disjoint union of two copies of the complete graph ${K_d }$ , for which the maximal eigenvalue is ${d }$ . Hence ${a(G) = n - \lambda_{\max}(G^c) = n-d = d }$ .

When ${ n = 2d-1}$ is odd, we have a natural candidate in ${ K_{d,d-1}}$ for which the argument from the previous paragraph shows ${a(G) = d-1 }$ . This is indeed a winner when ${n=5, d=3 }$ :

nd5-3-6 — 5 vertices, max degree 3, with a = 2

The winner is not unique since one can add another edge between two of the vertices of degree 2. This does not change the ${a(G)}$ , however: there is a fundamental eigenfunction that has equal values at the vertices of that added edge.

Same for ${n=9, d=5 }$ : the complete bipartite graph shares the maximum value of algebraic connectivity with two other graphs formed by adding edges to it:

nd9-5-22206 — 9 vertices, max degree 5, with a = 4

However, the family ${ K_{d,d-1}}$ does not win the case ${ n = 2d-1}$ in general: we already saw a 4-regular graph on 7 vertices with ${a(G)\approx 3.2 }$ , beating ${ a(K_{4, 3}) = 3}$ . Perhaps ${ K_{d,d-1}}$ wins when ${ d}$ is odd?

I do not have any other patterns to conjecture, but here are two winners for ${ n = 8, d= 3}$ : the cube and the “twisted cube”.

nd8-3-4326 — 8 vertices, max degree 3, with a = 2

nd8-3-8725 — 8 vertices, max degree 3, with a = 2

The cube is twisted by replacing a pair of edges on the top face with the diagonals. This is still a 3-regular graph and the algebraic connectivity stays the same, but it is no longer bipartite: a 5-cycle appears.

Measuring the regularity of a graph by its Laplacian eigenvalues

Let ${G}$ be a graph with vertices ${1, 2, \dots, n}$ . The degree of vertex ${i}$ is denoted ${d_i}$ . Let ${L}$ be the Laplacian matrix of ${G}$ , so that ${L_{ii}=d_i}$ , ${L_{ij}}$ is ${-1}$ when the vertices ${i, j}$ are adjacent, and is ${0}$ otherwise. The eigenvalues of ${L}$ are written as ${\lambda_1\le \dots \le \lambda_n}$ .

The graph is regular if all vertices have the same degree: ${d_1=\cdots = d_n}$ . How can this property be seen from its Laplacian eigenvalues ${\lambda_1, \dots, \lambda_n}$ ?

Since the sum of eigenvalues is equal to the trace, we have ${\sum \lambda_i = \sum d_i}$ . Moreover, ${\sum \lambda_i^2}$ is the trace of ${L^2}$ , which is equal to the sum of the squares of all entries of ${L}$ . This sum is ${\sum d_i^2 + \sum d_i}$ because the ${i}$ th row of ${L}$ contains one entry equal to ${d_i}$ and ${d_i}$ entries equal to ${-1}$ . In conclusion, ${\sum d_i^2 = \sum \lambda_i^2 - \sum\lambda_i}$ .

The Cauchy-Schwarz inequality says that ${n\sum d_i^2 \ge \left(\sum d_i \right)^2}$ with equality if and only if all numbers ${d_i}$ are equal, i.e., the graph is regular. In terms of eigenvalues, this means that the difference
$D =n\sum d_i^2 - \left(\sum d_i \right)^2 = n\sum (\lambda_i^2 - \lambda_i) - \left( \sum\lambda_i \right)^2$
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, ${D }$ is an even integer. Indeed, the sum ${\sum d_i}$ is even because it double-counts the edges. Hence the number of vertices of odd degree is even, which implies that ${\sum d_i^k }$ is even for every positive integer ${k }$ .

Up to a constant factor, ${D}$ is simply the degree variance: the variance of the sequence ${d_1, \dots, d_n}$ . What graph maximizes it for a given ${n}$ ? We want to have some very large degrees and some very small ones.

Let ${G_{m, n}}$ be the union of the complete graph ${K_m}$ on ${m}$ vertices and ${(n-m)}$ isolated vertices. The sum of degrees is ${m(m-1)}$ and the sum of squares of degrees is ${m(m-1)^2}$ . Hence,

${D = nm(m-1)^2 - (m(m-1))^2 = m(m-1)^2(n-m)}$

For ${n=3, 4, 5, 6}$ the maximum is attained by ${m=n-1}$ , that is there is one isolated vertex. For ${n=7, 8, 9, 10}$ the maximum is ${m=n-2}$ . In general it is attained by ${m^*=\lfloor (3n+2)/4 \rfloor}$ .

The graph ${G_{m, n}}$ is disconnected. But any graph has the same degree variance as its complement. And the complement ${G^c(m, n)}$ is always connected: it consists of a “center”, a complete graph on ${n-m}$ vertices, and “periphery”, a set of ${m}$ vertices that are connected to each central vertex. Put another way, ${G^c(m, n)}$ is obtained from the complete bipartite graph ${K_{m, n-m}}$ by connecting all vertices of the ${n-m}$ group together.

Tom A. B. Snijders (1981) proved that ${G(m^*, n)}$ and ${G^c(m^*, n)}$ are the only graphs maximizing the degree variance; in particular, ${G^c(m^*, n)}$ is the unique maximizer among the connected graphs. It is pictured below for ${n=4, \dots, 9}$ .

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.

8 vertices

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

Degree 3 regular:

8-6409 — 0.763932, 2, 4, 4, 4, 4, 5.236068

8-6579 — 1.438447, 2.381966, 2.381966, 3, 4.618034, 4.618034

8-6716 — 1.267949, 2, 2.585786, 4, 4, 4.732051,
5.414214

8-8725 — 2, 2, 2.585786, 2.585786, 4, 5.414214,
5.414214

Degree 4 regular

8-9570 — 2.763932, 4, 4, 4, 4, 6, 7.236068

8-10188 — 2.438447, 3.381966, 3.381966, 5, 5.618034, 5.618034, 6.561553

8-10202 — 2.585786, 3.267949, 4, 4, 5.414214, 6, 6.732051

8-10819 — 2.585786, 2.585786, 4, 5.414214, 5.414214, 6, 6

Degree 5 regular

8-10481 — 4.381966, 4.381966, 5, 5, 6.618034, 6.618034, 8

8-11082 — 4, 4.585786, 4.585786, 6, 6, 7.414214, 7.414214

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.

The infinitely big picture: tanh-tanh scale

When plotting the familiar elementary functions like x² 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 ${\tanh^{-1}x}$ or ${\frac12 \log((1+x)/(1-x))}$ , whatever you prefer to call it, does the opposite. So, conjugating any function ${f\colon \mathbb R\to \mathbb R}$ by the hyperbolic tangent produces a function ${g\colon (-1, 1)\to (-1,1)}$ 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 ${f(x) = \log|\coth(x/2)|}$ . Here it is shown in the normal coordinate system.

Graphs with an invertible incidence matrix

Graphs are often encoded by their adjacency matrix: a symmetric matrix where ${1}$ in the entry ${(i,j)}$ means there is an edge between vertices labeled ${i}$ and ${j}$ . Another useful encoding is the incidence matrix, in which rows correspond to edges and columns to vertices (or the other way around). Having ${1}$ in the entry ${(i,j)}$ means that ${i}$ th edge is incident to ${j}$ 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

${M = \displaystyle \begin{pmatrix} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \end{pmatrix}}$

(up to relabeling of vertices). This matrix is not invertible. Indeed, ${M(1,-1,1,-1)^T=0}$ , which is a reflection of the fact that the graph is bipartite. Indeed, for any bipartite graph the ${\pm 1}$ 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:

graph7_4

graph8_52

graph8_7

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

Random graphs with two-sided degree bounds

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.

g20-1-5 — 20 vertices, degree from 1 to 5

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

One more time:

g25-2-4 — 25 vertices, degree from 2 to 4