Proof of a conjecture on the algebraic connectivity of a graph and its complement
share
For a graph G, let λ_2(G) denote its second smallest Laplacian eigenvalue. It was conjectured that λ_2(G) + λ_2(G) ≥ 1, where G̅ is the complement of G. Here, we prove this conjecture in the general case. Also, we will show that {λ_2(G), λ_2(G)}≥ 1 - O(n^-1/3), where n is the number of vertices of G.
READ FULL TEXT