Spectral Gap of the Largest Eigenvalue of the Normalized Graph Laplacian

Abstract

We offer a new method for proving that the maxima eigenvalue of the normalized graph Laplacian of a graph with n vertices is at least $\frac{n+1}{n-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 $\frac{n-1}{2}$. 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 $\frac{n-1}{2}$.

Keywords

Spectral graph theory / Normalized Laplacian / Largest eigenvalue / Sharp bounds

References

[1] Atay FM, Tuncel H. On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication. Linear Algebra Appl.. 2014, 442 1 165-177

[2] Chung F. Spectral Graph Theory. 1997 Providence: American Mathematical Society

[3] Das K, Sun S. Extremal graph on normalized Laplacian spectral radius and energy. Electron. J. Linear Algebra. 2016, 29 1 237-253

[4] Li J, Guo J-M, Shiu WC. Bounds on normalized Laplacian eigenvalues of graphs. J. Inequal. Appl.. 2014, 2014 1 316

[5] Lin H, Zhai M, Gong S. On graphs with at least three distance eigenvalues less than $-1$. Linear Algebra Appl.. 2014, 458 548-558

Funding

Max Planck Institute for Mathematics in the Sciences (2)