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

spectral graph theorylargest eigenvaluenormalized Laplaciansharp bounds

Mathematics Subject Classification ID

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

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$.

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

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Bounds on normalized Laplacian eigenvalues of graphs
• 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

(10)

• Extremal normalized Laplacian spectral radii of graphs
• A new upper bound on the largest normalized Laplacian eigenvalue
• Bounding the gap between extremal Laplacian eigenvalues of graphs
• Minimum vertex covers and the spectrum of the normalized Laplacian on trees
• Petals and books: The largest Laplacian spectral gap from 1
• Metric uniformization and spectral bounds for graphs
• Graphs, Simplicial Complexes and Hypergraphs: Spectral Theory and Topology
• The maximum relaxation time of a random walk
• Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
• Cheeger‐like inequalities for the largest eigenvalue of the graph Laplace operator

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)