Spectral gap of the largest eigenvalue of the normalized graph Laplacian

DOI10.1007/S40304-020-00222-7MaRDI QIDQ2674036zbMATH OpenOpenAlexFDO

Authors R. Mulas, Florentin Münch, Jürgen Jost

Publication date 22 September 2022

Published in Communications in Mathematics and Statistics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.14402

zbMATH Keywords

largest eigenvaluenormalized Laplaciansharp boundsspectral graph theory

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Inequalities involving eigenvalues and eigenvectors (15A42)

Abstract: We offer a new method for proving that the maximal eigenvalue of the normalized graph Laplacian of a graph with $n$ vertices is at least $fracn+1n-1$ provided the graph is not complete and that equality is attained if and only if the complement graph is a single edge or a complete bipartite graph with both parts of size $fracn-12$. With the same method, we also prove a new lower bound to the largest eigenvalue in terms of the minimum vertex degree, provided this is at most $fracn-12$.

Review text

Let \(\lambda_n(G)\) denote the largest normalized Laplacian eigenvalue of a graph \(G\) of order \(n\). It has been known that \(\lambda_n(G) \ge \frac{n}{n-1}\) where equality is attained if and only if \(G\) is a complete graph; and that when \(G\) is not a complete graph, then \(\lambda_n(G) \ge \frac{n+1}{n-1}\) with the extremal graphs well-characterized. A new method is found in this study for proving these results. Using the same method, a new lower bound to the largest eigenvalue in terms of the minimum vertex degree is also found, provided this is at most \(\frac{n-1}{2}\).

Recommendations

• Bounding the gap between extremal Laplacian eigenvalues of graphs
• Bounds on normalized Laplacian eigenvalues of graphs
• Bounds on normalized Laplacian eigenvalues of graphs
• The largest normalized Laplacian spectral radius of non-bipartite graphs
• On the spectrum of the normalized graph Laplacian
• On the second largest normalized Laplacian eigenvalue of graphs
• The upper bounds for the largest Laplacian eigenvalue of graphs
• Normalized Laplacian spectrum of a graph and majorization
• The first two largest eigenvalues of Laplacian, spectral gap problem and Cheeger constant of graphs
• Bounds for the largest \(p\)-Laplacian eigenvalue for graphs

Cites work

• Bounds on normalized Laplacian eigenvalues of graphs
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• On graphs with at least three distance eigenvalues less than \(-1\)
• On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication

Cited in

(14)

• The maximum relaxation time of a random walk
• Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
• Bounding the gap between extremal Laplacian eigenvalues of graphs
• A new upper bound on the largest normalized Laplacian eigenvalue
• Minimum vertex covers and the spectrum of the normalized Laplacian on trees
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator
• Petals and books: The largest Laplacian spectral gap from 1
• Extremal normalized Laplacian spectral radii of graphs
• Metric uniformization and spectral bounds for graphs
• On the spectral gap of a discrete Schrödinger operator on the path graph in the limit of large volume
• Chern-Simons-Higgs type equations on canonically compactifiable graphs
• Characterization of graphs with some normalized Laplacian eigenvalue having multiplicity n-4
• Extremal graphs minimizing the normalized Laplacian spectral radius

This page was built for publication: Spectral gap of the largest eigenvalue of the normalized graph Laplacian

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2674036)