Petals and Books: The largest Laplacian spectral gap from 1

Abstract

We prove that, for any connected graph on $N\ge 3$ vertices, the spectral gap from the value $1$ with respect to the normalized Laplacian is at most $1/2$. Moreover, we show that equality is achieved if and only if the graph is either a petal graph (for $N$ odd) or a book graph (for $N$ even). This implies that $(\frac{1}{2},\frac{3}{2})$ is a maximal gap interval for the normalized Laplacian on connected graphs. This is closely related to the Alon-Boppana bound on regular graphs and a recent result by Kollár and Sarnak on cubic graphs. Our result also provides a sharp bound for the convergence rate of some eigenvalues of the Laplacian on neighborhood graphs.

32 pages

References in corpus (2)

• Line-Graph Lattices: Euclidean and Non-Euclidean Flat Bands, and Implementations in Circuit Quantum Electrodynamics
• Spectral gap of the largest eigenvalue of the normalized graph Laplacian

Cited by in corpus (1)

• Homological eigenvalues of graph $p$-Laplacians