The Algebraic Connectivity of a Graph and its Complement

Abstract

For a graph $G$, let ${\lambda }_2(G)$ denote its second smallest Laplacian eigenvalue. It was conjectured that ${\lambda }_2(G)+{\lambda }_2(\overline{G})\ge 1$, where $\overline{G}$ is the complement of $G$. In this paper, it is shown that $\max \{{\lambda }_2(G),{\lambda }_2(\overline{G})\}\ge 2/5$.