A Nordhaus-Gaddum type problem for the normalized Laplacian spectrum and graph Cheeger constant

Abstract

For a graph on $n$ vertices with normalized Laplacian spectra $0 = \lambda_1(G) \leq \lambda_2(G) \leq \cdots \leq \lambda_n(G)$, we show that $$ \max\{\lambda_2(G), \lambda_2(G^c)\} \geq \frac{2}{n^2} $$ by proving a lower bound on the Cheeger constant and graph isoperimetric number.