Adjacency, Laplacian and Maximum Degree

Question

I am relevantly new to https://math.stackexchange.com/ and this will be my first question, although I have been lurking around for some time now! So, pardon me if I am missing any posting etiquette rules.

What I have been looking for a while is a connection between the spectra of the Adjacency $(\lambda_i(A))$ and Laplacian $(\lambda_i(L))$ matrices in terms of the Maximum degree $(\Delta)$ of a graph $G$. I am not certain that there is one, although I have been hinted towards believing so.

So, ideally, I am looking for a relation similar to the one holding for $d-$regular graphs:

$$\lambda_i(L) = d - \lambda_{n-i+1}(A).$$

Does anyone have any clues? I understand that a result will not be as universal as the above, or as powerful, otherwise it would be widely known, but I am hoping for anything here.

Thanks in advance for your time!

Cheers,

kxk

Answer 1

I seem to have found a result after all. Apparently there is the following connection.

Again let $G$ be a graph on $n$ vertices with largest degree $\Delta$, adjacency matrix $A$ and Laplacian $L$, then:

$$\Delta - \lambda_n(A) \leq \lambda_n(L) \leq \Delta - \lambda_1(A)$$

So, impressively enough there is a connection and for some reason I am inclined to believe that there might be even more results.

Answer 2

There is not really any connection between the spectrum of the adjacency matrix of a graph an the spectrum of of its Laplacian, regular graphs aside. One simple illustration of this is that there any pairs of graphs whose adjacency matrices are similar, but whose Laplacians are not. For example, take the complete bipartite graph $K_{1,4}$ and the disjoint union of a 4-cycle and an isolated vertex.

If you are interested in questions like these, you might one to learn to use a software package such as sage (which I just used to check the above example).