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

Abstract

For a graph $G$ on $n$ vertices with normalized Laplacian eigenvalues $0={\lambda }_1(G)\le {\lambda }_2(G)\le \cdots \le {\lambda }_n(G)$ and graph complement $G^c$, we prove that \begin{equation*} \max\{λ_2(G),λ_2(G^c)\}\geq \frac{2}{n^2}. \end{equation*} We do this by way of lower bounding $\max \{i(G),i(G^c)\}$ and $\max \{h(G),h(G^c)\}$ where $i(G)$ and $h(G)$ denote the isoperimetric number and Cheeger constant of $G$, respectively.