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

J. Nolan Faught, Mark Kempton, Adam Knudson

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*} \…