The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

126 Views Asked by At

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the eigenvalue of the Laplacian. I would like to find some statistic result, namely, "in general" how the $\sigma_i$ would change when we add edge to the graph.

Attempts:

1.I looked into the properties of the spectra in the determinant case, there seems to be some theorems such as eigenvalue interlacing, but we still cannot say anything about it.

2.So I looked into the random graph, hoping to find some relevant statistical spectra properties. There are some results but most of them seems to be bounds and studies about the case when $n\rightarrow\infty$. I think now most of the papers use the model of $G(n,p)$ instead of $G(n,m)$. My idea is to check the spectra properties of $G(n,m)$ and $G(n,m+k)$, where $k>0$. But unfortunately, I wasn't able to find relevant papers for that.

It would be grateful if someone could help.