On the lower bound of the sum of the algebraic connectivity of a graph and its complement (Q1984518)

Let \(G\) be a simple graph with \(n\) vertices. The Laplacian matrix of \(G\) is defined to be \(L:=D-A\), where \(A\) is the adjacency matrix of \(G\) and \(D\) is the diagonal matrix of vertex degrees. Let \(0=\mu_1(G)\leq\mu_2(G)\leq\cdots\leq\mu_n(G)\) be the eigenvalues of \(L\). The Laplacian spread of a graph \(G\) is defined to be \(\mu_n(G)-\mu_2(G)\). In [\textit{Z. You} and \textit{B. Liu}, Czech. Math. J. 62, No. 1, 155--168 (2012; Zbl 1245.05089); \textit{M. Zhai} et al., Appl. Math. Lett. 24, No. 12, 2097--2101 (2011; Zbl 1234.05156)], it was conjectured that this quantity is at most \(n-1\), or equivalently, \(\mu_2(G)+\mu_2(\overline{G})\) is at least \(1\), where \(\overline{G}\) is the complement of \(G\). This conjecture has been proved for various families of graphs. In this paper, the authors prove this conjecture in the general case. Also, they show that \(\max\{\mu_2(G),\mu_2(\overline{G})\} \geq 1 -O(n^{-\frac{1}{3}})\), where \(n\) is the number of vertices of \(G\).