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.

The effect of adding an edge on Laplacian eigenvalues

Normalized Laplacian

The opposite direction

Related

Leave a Reply Cancel reply