Algebraic connectivity supremum for graph-complement pairs

Status partial high confidence

The closing question asks for the exact supremum c such that max{\lambda_2(G), \lambda_2(\bar{G})} \geq c holds for all graphs G of order at least 2; the source paper proved c \geq 2/5. Einollahzadeh and Karkhaneei (arXiv:1901.02047, 2019) subsequently proved the sum conjecture \lambda_2(G) + \lambda_2(\bar{G}) \geq 1, which implies max{\lambda_2(G), \lambda_2(\bar{G})} \geq 1/2, improving the lower bound. The exact supremum remains open, lying in the interval [1/2,\, 2-\sqrt{2}] \approx [0.5, 0.5858], where the upper bound comes from the self-complementary path P_4.

Cited literature (1)

• partial Proof of a conjecture on the algebraic connectivity of a graph and its complement (2019)
  Mostafa Einollahzadeh, Mohammad Mahdi Karkhaneei · arXiv preprint · arXiv:1901.02047

  Proves \lambda_2(G) + \lambda_2(\bar{G}) \geq 1 for all graphs G, which implies max{\lambda_2(G), \lambda_2(\bar{G})} \geq 1/2, thereby improving the lower bound on the supremum from 2/5 to 1/2.

Reviewer notes. The sum conjecture \lambda_2(G)+\lambda_2(\bar{G}) \geq 1, proved in arXiv:1901.02047, gives partial progress by improving the lower bound on the supremum from 2/5 to 1/2. The exact supremum remains open; no paper resolving it was found in the indexed literature.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).