Abstract
We prove that, for any connected graph on (Figure presented.) 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 (Figure presented.) odd) or a book graph (for (Figure presented.) even). This implies that (Figure presented.) 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.
| Original language | English |
|---|---|
| Pages (from-to) | 727-756 |
| Number of pages | 30 |
| Journal | Journal of Graph Theory |
| Volume | 104 |
| Issue number | 4 |
| Early online date | 5 Jul 2023 |
| DOIs | |
| Publication status | Published - Dec 2023 |
Bibliographical note
Funding Information:The authors are grateful to the anonymous referees for their comments and suggestions. Raffaella Mulas was supported by the Max Planck Society's Minerva Grant. Open Access funding enabled and organized by Projekt DEAL.
Publisher Copyright:
© 2023 The Authors. Journal of Graph Theory published by Wiley Periodicals LLC.
Keywords
- eigenvalue 1
- maximal gap interval
- neighborhood graph
- normalized Laplacian
- spectral gaps
- spectral graph theory