Nordhaus-Gaddum Type Inequalities for the kth Largest Laplacian Eigenvalues

Let G be a simple connected graph and μ₁(G) ≥ μ₂(G) ≥ ⋯ ≥ μₙ(G) be the Laplacian eigenvalues of G. Let Ḡ be the complement of G. Einollahzadeh et al.[J. Combin. Theory Ser. B, 151(2021), 235–249] proved that μₙ₋₁(G)+μₙ₋₁(Ḡ)≥ 1. Grijò et al. [Discrete Appl. Math., 267(2019), 176–183] conjectured that μₙ₋₂(G)+μₙ₋₂(Ḡ)≥ 2 for any graph and proved it to be true for some graphs. In this paper, we prove μₙ₋₂(G)+μₙ₋₂(Ḡ)≥ 2 is true for some new graphs. Furthermore, we propose a more general conjecture that μₖ(G)+μₖ(Ḡ)≥ n-k holds for any graph G, with equality if and only if G or Ḡ is isomorphic to Kₙ₋ₖ H, where H is a disconnected graph on k vertices and has at least $n-k+1$ connected components. And we prove that it is true for k≤ n+1/2, for unicyclic graphs, bicyclic graphs, threshold graphs, bipartite graphs, regular graphs, complete multipartite graphs and c-cyclic graphs when n≥ 2c+8.