On the \(k\)th largest eigenvalue of the Laplacian matrix of a graph (Q5942761)

The authors give upper and lower bounds on the \(k\)th largest eigenvalue \(\lambda_k\) of the Laplacian matrix of a graph \(G\) in terms of the edge number of \(G\) and the number of spanning trees of \(G\). More precisely, for a graph \(G\) with \(n\) vertices let \(\lambda_1\geq\lambda_2\geq\dots\geq\lambda_{n-1}\geq\lambda_n=0\) be the eigenvalues of the Laplacian matrix of \(G\), and let \(e(G)\) and \(c(G)\) denote the number of edges of \(G\) and the number of spanning trees of \(G\), respectively. The authors prove the following theorems giving upper and lower bounds on the Laplacian eigenvalues: Theorem 2.1. Let \(G\) be a simple graph with \(n\) vertices. Then \[ \begin{aligned} \lambda_1 &\geq \frac 1{n-1} \left\{2e(G)+\sqrt{\frac{2e(G)(n(n-1)-2e(G))}{n(n-2)}}\right\} \\ \lambda_{n-1} &\leq \frac 1{n-1} \left\{2e(G)-\sqrt{\frac{2e(G)(n(n-1)-2e(G))}{n(n-2)}}\right\}, \end{aligned} \] where the equality in either of these inequalities holds if and only if \(G\) is a complete graph \(K_n\). Theorem 3.3. Let \(G\) be a graph with \(n\) vertices. Write \(M(G)=\min\{e(G)((n-4)e(G)+2(n-1)), 2e(G)(n(n-1)-2e(G))\}\). Then for \(k=1,2,\dots, n-1\) \[ \lambda_k\leq \frac 1{n-1} \left\{2e(G)+\left[\frac{n-k-1}n M(G)\right]^{1/2}\right\} \] with equality holding for some \(k\) if and only if \(G\) is \(K_n\) or \(K_{1,n-1}\). Theorem 3.4. Let \(G\) be a \(d\)-regular graph with \(n\) vertices. Then for \(k=1,2,\dots,k-1\) \[ \lambda_k\leq\frac 1{n-1} \left\{nd+\sqrt{\frac{n-k-1}n dn(n-d-1)}\right\} \] with equality holding for some \(k\) if and only if \(G\) is a strongly regular graph or \(K_n\). Theorem 3.6. Let \(G\) be a graph with \(n\) vertices. Then for \(k=2,3,\dots,n-1\) \[ \lambda_k\geq\frac 1{n-k} \left\{(n-1)(2^{n-k}nc(G))^{\frac 1{n-1}}-2e(G)\right\} \] with equality holding if \(k=(m-1)^2+1\) and \(G\) is a strongly regular graph with the parameters \((m^2,2(m-1),m-2,2)\). Theorem 3.8. Let \(G\) be a graph with \(n\) vertices. Then for \(k=2,3,\dots,n-1\) \[ \lambda_k\geq \left\{ nc(G) \left( \frac{k-1}{2e(G)} \right)^{k-1} \right\}^{\frac 1{n-k}}. \] Regarding lower bounds an important fact is that they are decreasing with \(k\).