Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).

Let $A$ be the adjacency matrix of $G$, i.e. the rows and columns are indexed by vertices of $G$ and $A_{u,v} = w_{u,v}$. Let $D$ be the diagonal degree matrix: $D_{u,u} = \deg(u) = \sum_v w_{u,v}$ and $D_{u,v} = 0$ for $u \neq v$. Let $L = D - A$ be the Laplacian matrix of the graph.

Both $A$ and $L$ are self-adjoint. Let $\mu_1 \leq \mu_2 \dotsb \leq \mu_n$ be the eigenvalues of $A$, and let $0 = \lambda_1 \leq \lambda_2 \leq \dotsb \leq \lambda_n$ be the eigenvalues of $L$.

I have run many tests, and it looks like the (top) spectral gap $\mu_n - \mu_{n-1}$ of $A$ is always at least as large as the (bottom) spectral gap $\lambda_2 - \lambda_1 = \lambda_2$ of $L$.

The two quantities are equal if $G$ is regular, i.e. all vertices have the same degree, because then $D = \deg(u) I$ for any vertex $u$ of $G$, and so the spectrum of $L$ is a shift and reflection of the spectrum of $A$. In my tests, as the difference between the maximum and minimum degrees of $G$ gets larger (i.e. as $G$ becomes "less regular"), the difference $(\mu_n - \mu_{n-1}) - \lambda_2$ gets larger as well (on average). The relationship seems to be rougly linear.

It seems to me like this should be a known phenomenon (if indeed it is true), but I haven't been able to find it anywhere in the literature. If anyone has seen this before, please let me know. Otherwise I'll just try to prove it myself.

  • $\begingroup$ Update: the relationship which I said "seems to be roughly linear" is actually not linear in general. The sequence of star graphs has (min degree - max degree) ~ n, but the difference between the spectral gaps is ~ sqrt(n). $\endgroup$ Jul 11, 2021 at 7:49
  • $\begingroup$ Another update: there is actually no correlation (in general) with (max degree - min degree). Let G be the graph on three vertices, where two of them have self-loops of weight n and the other one has degree 0. Then (max degree - min degree) = n, but the spectral gaps of A and L are both 0. $\endgroup$ Jul 12, 2021 at 15:00

1 Answer 1


Well, I found a counterexample (actually, many) to this claim. In fact, it only has 7 vertices: it is given by the graph6 string "F{O_w". Here's a picture:

enter image description here

Now the question becomes whether there is a sequence of graphs with Laplacian spectral gap bounded away from 0 and Adjacency spectral gap approaching 0. So far, I have not found any such sequence.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .