Spectral gap of the largest eigenvalue of the normalized graph Laplacian

DOI10.1007/S40304-020-00222-7zbMATH Open1503.05076arXiv1910.14402OpenAlexW3151254556MaRDI QIDQ2674036FDOQ2674036

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)

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• 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)

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

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)