Stevanović's Nordhaus–Gaddum extremal conjecture for graph spectral radius

Let GG be a simple undirected graph of order nn, with adjacency matrix A(G)A(G) and spectral radius ρ(G)=ρ(A(G))\rho(G)=\rho(A(G)). For a graph GG, let G\overline{G} denote its complement. For vertex-disjoint graphs GG and HH, let GHG\vee H be their join; write KqK_q for the complete graph of order qq and NqN_q for the null graph of order qq. A graph KqNnqK_q\vee N_{n-q} is called a complete split graph.

Stevanović's conjecture. The maximum value of

ρ(G)+ρ(G)\rho(G)+\rho(\overline{G})

among graphs GG of order nn is attained by the complete split graph Kn3N2n3K_{\lfloor\frac{n}{3}\rfloor}\vee N_{\lceil\frac{2n}{3}\rceil} and its complement. If n2(mod3)n\equiv 2 \pmod{3}, the maximum is also attained by Kn3N2n3K_{\lceil\frac{n}{3}\rceil}\vee N_{\lfloor\frac{2n}{3}\rfloor} and its complement.

This is a Nordhaus–Gaddum type extremal problem for the spectral radius. The paper's abstract states that the authors determine the extremal graph, thereby resolving the conjecture.

Sources & referencesView supporting material

Primary source

Yen-Jen Cheng and Chih-wen Weng, “Nordhaus-Gaddum inequality for the spectral radius of a graph of order n”, arXiv:2506.11401 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.