A Conjecture on the Nordhaus-Gaddum Product Type Inequality for Laplacian Eigenvalue of a Graph

Abstract

For a graph $G$ of $n$ vertices, let $\mu_{1}(G)$ be its largest Laplacian eigenvalue. It was conjectured by Ashraf et al. in [Electron. J. Combin. 21(3):#P3.6 (2014) that
$$ \mu_{1}(G) \mu_{1}(\bar{G}) \leqslant n(n-1), $$
where $\bar{G}$ is the complement of $G$, and equality holds if and only if $G$ or $\bar{G}$ is isomorphic to the join of an isolated vertex and a disconnected graph of order $n-1$.

They proved that this conjecture holds for bipartite graphs. In this paper, we completely confirm this conjecture. Furthermore, we propose a more general conjecture that for any graph $G$ with $n$ vertices and $k \leq \frac{3n}{4}$,
$$ \mu_k(G) \mu_k(\bar{G})\leq n(n-k), $$
and equality holds if and only if $G$ or $\bar{G}$ is isomorphic to the join of $K_{k}$ and a disconnected graph on $n-k$ vertices and has at least $k+1$ connected components.

We also prove that it is true for $\frac{n}{2}\leq k \leq \frac{3n}{4}$, and for each $k \geq \frac{3n}{4}+1$, a counterexample is given.