文献类型：期刊文献

英文题名：A conjecture on the Nordhaus-Gaddum product type inequality for Laplacian eigenvalues of a graph

作者：Chen, Qi[1];Guo, Ji-Ming[1];Li, Wen-Jun[2];Wang, Zhiwen[1]

机构：[1]East China Univ Sci & Technol, Sch Math, Shanghai, Peoples R China;[2]Changzhou Inst Technol, Sch Sci, Changzhou, Peoples R China

年份：2025

卷号：32

期号：4

外文期刊名：ELECTRONIC JOURNAL OF COMBINATORICS

收录：;WOS:【SCI-EXPANDED(收录号:WOS:001609620300001)】；

基金：Acknowledgements Ji-Ming Guo received support from National Natural Science Foundation of China (Grant No. 12171154) . Zhiwen Wang is supported by National Natural Science Foundation of China (Grant No. 12301438) , Chenguang Program of Shanghai Education Development Foundation and Shanghai Municipal Education Commission (Grant No. 23CGA37) and Youth Innovation Team Project of Shandong Province Universities (Grant No. 2023KJ353) .

语种：英文

摘要：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 )(G) <= n(n - 1), where G(-) is the complement of G, and equality holds if and only if G or 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 nvertices and k <= 3n/4, mu(k )(G)mu(k)(G) <= n(n - k), and equality holds if and only if G or G is isomorphic to the join of Kk and a disconnected graph on n - k vertices with at least k + 1 connected components. We also prove that it is true for n/2 <= k <= 3n/4, and for eachk <= 3n/4 + 1, a counterexample is given.