When is this graph Laplacian inequality true?

90 Views Asked by At

Let $G$ be a simple, connected graph on $n$ vertices, and let $0 = \mu_1 < \mu_2 \le \cdots \le \mu_n$ and $\lambda_1 > \lambda_2 \ge \cdots \ge \lambda_n$ be the eigenvalues of $G$'s Laplacian and adjacency matrices, respectively. I am interested in determining when the inequality $$\delta \le \frac{\mu_2 + \mu_n}{2}$$ is true (where $\delta$ is the minimum degree of $G$). I don't believe it is always true, since if we consider a $d$-regular graph, we find that $$\delta > \frac{\mu_2 + \mu_n}{2} \Longleftrightarrow 2d > (d-\lambda_2) + (d-\lambda_n) \Longleftrightarrow \lambda_2 > |\lambda_n|,$$ which I believe I've seen before for some graphs.

From some searching, I've been able to find that $$\mu_2 \le \frac{n}{n-1}\delta \le \frac{n}{n-1}\Delta \le \mu_n,$$ ($\Delta$ is maximum degree of $G$) but I haven't been able to figure anything out just from that. Thank you for your help!