A conjecture on the Nordhaus-Gaddum product type inequality for Laplacian eigenvalue of a graph

Qi Chen ; Ji-Ming Guo¹ ; Wen-Jun Li ; Zhiwen Wang¹

¹East China University of Science and Technology

The electronic journal of combinatorics, Tome 32 (2025) no. 4

Résumé

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.

Détail

DOI : 10.37236/14060

Classification : 05C50, 15A18
Mots-clés : largest Laplacian eigenvalue