# Relationship between spectral gaps of adjacency and Laplacian matrices of graphs

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.

• 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). Jul 11 at 7:49
• 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. Jul 12 at 15:00