Bounding the gap between extremal Laplacian eigenvalues of graphs (Q2497240)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bounding the gap between extremal Laplacian eigenvalues of graphs |
scientific article |
Statements
Bounding the gap between extremal Laplacian eigenvalues of graphs (English)
0 references
4 August 2006
0 references
Let \(G\) be a graph whose Laplacian eigenvalues are \(0=\lambda_{1}\leq \lambda_{2}\leq \dots\leq \lambda_{n}\). Motivated by the property of extremal Laplacian eigenvalues to provide a possible value range for the density of cuts in a graph, the author is interested in providing lower bounds on the gaps \(\frac{\lambda_{n}}{\lambda_{2}}\) and \(\lambda_{n} - \lambda_{2}\) between the extremal non-trivial Laplacian eigenvalues in a connected graph. The author first observes a simple ratio bound \[ \frac{\lambda_{n}}{\lambda_{2}}\geq\frac{\Delta(G)+1}{\delta(G)}, \] characterizes the case of equality and then conjectures that this bound can be further improved by \(O(\frac1{n^{2}})\) a.e. for random graphs. Further, the author uses two reverse Cauchy-Schwarz inequalities, that is the Pólya-Szegö inequality and the Ozeki inequality, to get additional lower bounds on \(\frac{\lambda_{n}}{\lambda_{2}}\) in Theorem 3.5 and on \(\lambda_{n} - \lambda_{2}\) in Theorem 3.6. At present, these theorems hold only for connected regular graphs, although they can be extended to hold for other graphs by letting the vector \(a\) in the proofs of these theorems be a vector of vertex degrees (either the \(n-1\) smallest or the \(n-1\) largest degrees).
0 references
Laplacian matrix
0 references
cut
0 references
reverse Cauchy-Schwarz inequality
0 references
Pólya-Szegö inequality
0 references
Ozeki inequality
0 references
0 references