Bounding the gap between extremal Laplacian eigenvalues of graphs
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).
- Spectral gap of the largest eigenvalue of the normalized graph Laplacian
- Upper bound for the Laplacian graph eigenvalues
- Bounds for Laplacian graph eigenvalues
- On the \(k\)th largest eigenvalue of the Laplacian matrix of a graph
- An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs
- A proof of Alon’s second eigenvalue conjecture and related problems
- An Upper Bound on the Diameter of a Graph from Eigenvalues Associated with Its Laplacian
- Eigenvalues, diameter, and mean distance in graphs
- scientific article; zbMATH DE number 1054729 (Why is no real title available?)
- scientific article; zbMATH DE number 2107630 (Why is no real title available?)
- scientific article; zbMATH DE number 867649 (Why is no real title available?)
- scientific article; zbMATH DE number 3373676 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- Laplacian graph eigenvectors
- Laplacian matrices of graphs: A survey
- On graphs with equal algebraic and vertex connectivity
- Open problems of Paul Erd�s in graph theory
- The Laplacian Spectrum of a Graph II
- Bounding the diameter and the mean distance of a graph from its eigenvalues: Laplacian versus adjacency matrix methods
- New lower bounds for the Randić spread
- Spectral gap of the largest eigenvalue of the normalized graph Laplacian
- Graph toughness from Laplacian eigenvalues
- Some remarks on Laplacian eigenvalues of connected graphs
- The Laplacian spread of graphs.
- Some results on the Laplacian spread of a graph
- On Laplacian eigenvalues of connected graphs.
- On the Laplacian spectral ratio of connected graphs
- Laplacian spread of graphs: lower bounds and relations with invariant parameters
- Gluing graphs and the spectral gap: a Titchmarsh–Weyl matrix-valued function approach
- Inequalities for real number sequences with applications in spectral graph theory
- Extremal Graph Realizations and Graph Laplacian Eigenvalues
- On the nontrivial extremal eigenvalues of graphs
- New bounds on the Laplacian spectral ratio of connected graphs.
This page was built for publication: Bounding the gap between extremal Laplacian eigenvalues of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2497240)
