Nordhaus-Gaddum type inequalities for Laplacian and signless Laplacian eigenvalues (Q405284)

Summary: Let \(G\) be a graph with \(n\) vertices. We denote the largest~signless~Laplacian eigenvalue of \(G\) by \(q_1(G)\) and~Laplacian eigenvalues of \(G\) by \(\mu_1(G)\geq\cdots\geq\mu_{n-1}(G)\geq\mu_n(G)=0\). It is a conjecture on Laplacian spread of graphs that \(\mu_1(G)-\mu_{n-1}(G)\leq n-1\) or equivalently \(\mu_1(G)+\mu_1(\overline G)\leq2n-1\). We prove the conjecture for~bipartite graphs. Also we show that for any bipartite graph \(G\), \(\mu_1(G)\mu_1(\overline G)\leq n(n-1)\). \textit{M. Aouchiche} and \textit{P. Hansen} [Discrete Appl. Math. 161, No. 4--5, 466--546 (2013; Zbl 1259.05083)] conjectured that \(q_1(G)+q_1(\overline G)\leq3n-4\) and \(q_1(G)q_1(\overline G)\leq2n(n-2)\). We prove the former and disprove the latter by constructing a family of graphs \(H_n\) where \(q_1(H_n)q_1(\overline{H_n})\) is about \(2.15n^2+O(n)\).