Nordhaus-Gaddum inequality for the spectral radius of a graph of order $n$

Chih-wen Weng; Yen-Jen Cheng

REVIEW 3 major objections 3 minor 1 cited by

Nordhaus-Gaddum inequality for the spectral radius of a graph of order $n$

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Complete split graphs maximize the spectral radius of a graph plus its complement, for every order.

desk verdict Settles a 2007 Nordhaus-Gaddum conjecture for all n; the main argument holds up, but Lemma 2.1's universality is asserted rather than proved. read the letter →

arxiv 2506.11401 v1 pith:CQC4JBPB submitted 2025-06-13 math.CO

Yen-Jen Cheng , Chih-wen Weng This is my paper · ORCID

classification math.CO MSC 05C5015A18

keywords nonnegativematricesspectralradiusboundsNordhaus-Gaddumtypeproblemcompletesplitgraphcomplementextremaladjacencymatrix

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper claims to settle a 2007 conjecture about the Nordhaus–Gaddum type behavior of the spectral radius. For every order $n$, the quantity $\rho(G)+\rho(\bar G)$ is maximized by the complete split graph $K_{\lfloor n/3\rfloor}\vee N_{\lceil 2n/3\rceil}$ and its complement, with a second extremizer when $n\equiv 2\pmod 3$. The proof works for all $n$ and uses only linear algebra, yielding the exact maximum in closed form. A reader should care because this closes a long-standing open problem and, as a corollary, confirms the conjectured bound $\rho(G)+\rho(\bar G)\le (4/3)n+O(1)$ with the explicit constant $1/3$.

What carries the argument

The carrying object is the staircase class $S^*_s(n)$: symmetric zero-diagonal $0$-$1$ matrices whose $1$'s fill a staircase shape, with corner conditions $a_{12}=1$ and $a_{n-1,n}=0$. The proof begins with the structural lemma that every extremal graph has a vertex ordering whose adjacency matrix lies in this class. For such a matrix $A$, three integer parameters $c,v,s$ record where the staircase stops, and mirrored parameters $\bar c,\bar v,\bar s$ are read from the reflected complement. A row-sum bound supplies the closed upper estimate $\rho(A)\le \phi(A)$ in terms of $(c,v,s)$, and a sequence of local staircase moves shows that no candidate can beat the complete split form. The final comparison is reduced to a quartic polynomial $g(x)$ that is increasing on the relevant interval, with one exceptional parameter triple excluded by a rooted-matrix bound and the characteristic polynomial of an explicit $6\times 6$ matrix.

What would settle it

For a fixed small $n$, exhaustively compute $\rho(G)+\rho(\bar G)$ over all unlabeled graphs of that order and check that the maximum agrees with the right-hand side of (4.3) and is attained only by the named complete split graphs; a single counterexample would refute the claim. Alternatively, in the exceptional case $(n,c,\bar c)=(3k+2,2k+1,2k+1)$, evaluate the spectral radius of the explicit $6\times 6$ matrix $M$ in Section 7: if it ever reaches $\rho_0=4k+1$, the exclusion argument fails.

Watch

Extended reading notes

Core claim

The paper's central claim is that the conjecture holds in full: among all simple graphs of order $n\ge 3$, the sum $\rho(G)+\rho(\bar G)$ is maximized by the complete split graph $K_{\lfloor n/3\rfloor}\vee N_{\lceil 2n/3\rceil}$ and by its complement, and when $n\equiv 2\pmod 3$ also by $K_{\lceil n/3\rceil}\vee N_{\lfloor 2n/3\rfloor}$ and its complement. A complete split graph is formed by joining a clique to an independent set with all possible edges, so its complement is a disjoint union of an independent set and a clique. The proof gives the exact maximum value in closed form as (4.3) and shows that the equality cases are exactly these graphs up to complementation. A direct corollary is the uniform bound $\rho(G)+\rho(\bar G)\le (4/3)n+1/3$.

Load-bearing premise

The proof depends on the structural lemma that every extremal graph, after relabeling, has its adjacency matrix in the staircase class; if some extremal graph lacked such an ordering, the whole reduction would only cover a subclass of candidates.

Editorial extensions

If this is right

The exact extremal value of $\rho(G)+\rho(\bar G)$ is known for every $n$ through the closed formula (4.3), so the maximum no longer needs to be estimated asymptotically.
Every extremal graph is classified: it is the complete split graph $K_{\lfloor n/3\rfloor}\vee N_{\lceil 2n/3\rceil}$, its complement, and additionally $K_{\lceil n/3\rceil}\vee N_{\lfloor 2n/3\rfloor}$ or its complement when $n\equiv 2\pmod 3$.
The uniform bound $\rho(G)+\rho(\bar G)\le (4/3)n+1/3$ follows, verifying the previously conjectured $4n/3+O(1)$ form.
Because the proof is purely linear algebraic, it covers all $n$ uniformly and does not rely on analytic large-$n$ methods.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same staircase-and-parameter strategy could plausibly transfer to other Nordhaus–Gaddum sums of spectral invariants, such as Laplacian or signless Laplacian eigenvalues, if an analogue of the structural lemma holds; the paper does not pursue this.
The equality analysis suggests a stability statement: graphs whose spectral sum is within $\varepsilon$ of the maximum should be close, in edge-edit distance, to the complete split extremizers. No such stability bound is proved here.
The explicit determinant computations in the exceptional case could be refined to extract a quantitative gap between subextremal graphs and the maximum, a testable extension of the same polynomial method.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Bottom line: this paper settles Stevanović's 2007 conjecture: for every n, the maximum of ρ(G)+ρ(\bar G) is attained by K_{⌊n/3⌋}∨N_{⌈2n/3⌉} and its complement, with an additional extremal graph when n≡2 mod 3. Previous work only gave asymptotic bounds (Terpai) or large-n proofs (Liu). That is a real closed problem, and the finite-n proof is a genuine contribution.

What the paper does well: the reduction to staircase matrices via Lemma 2.1 is the right structural framework; the upper bound ϕ(A) obtained from Csikvári's row-sum bound is used cleverly; the case analysis is detailed, and the last remaining case (n=3k+2, c=c̄=2k+1) is handled by a concrete 6×6 matrix argument. The chain of inequalities in Sections 6–7 is intricate but internally consistent as far as I checked. The paper also recovers Nikiforov's conjecture as a corollary. The citations to the authors' own earlier work are to published theorems, so I do not see a circularity problem.

The main soft spot is the status of Lemma 2.1. As stated, it says every extremal graph has a vertex ordering with adjacency matrix in S*_s(n), but Remark 2.2 only asserts that Csikvári's proof shows this, without giving the precise theorem or the argument. If the actual Csikvári result is only that some extremal graph lies in the staircase class, then the paper's claim that every extremal graph is complete split (or its complement) does not follow from the present argument. The conjecture itself can still be recovered: apply the whole chain to that extremal representative and the maximum value is the complete split value. So this is a significant but patchable gap: the authors should pin down the exact statement and prove the universal direction, or soften the classification claim. A couple of lemmas (3.4, 3.5) are sketched with 'similar to' earlier proofs, which slows independent verification. I did not find a decisive error elsewhere.

Who it is for: spectral graph theorists, especially people working on Nordhaus–Gaddum problems or extremal spectral bounds. It deserves a serious referee; I would send it to review, with the request that the authors clarify Lemma 2.1 and expand the sketched parts.

Referee Report

3 major / 3 minor

Summary. The paper studies the Nordhaus-Gaddum problem for the spectral radius and claims to resolve Stevanović's 2007 conjecture: for every n, the maximum of ρ(G)+ρ(\bar G) over n-vertex graphs is attained by the complete split graph K_{⌊n/3⌋}∨N_{⌈2n/3⌉}, and, when n≡2 (mod 3), also by K_{⌈n/3⌉}∨N_{⌊2n/3⌋}. The proof uses Csikvári's reduction to staircase matrices, introduces parameters c,v,s and their complement counterparts, derives upper bounds φ(A) and φ(\bar A), then reduces to five residue-class cases and one exceptional case, which is handled by a Kronecker-sum matrix argument. The final section claims that every graph attaining the maximum is a complete split graph or its complement.

Significance. If correct, this is a complete proof of a conjecture that was previously known only for large n via analytic methods, and it is notable for being purely linear algebraic. The paper makes explicit parameter computations, gives equality cases for the row-sum bounds, and reduces the problem to a finite case analysis; these are concrete and checkable strengths. The main caveat is the dependence on the exact quantifier in Lemma 2.1, discussed below.

major comments (3)

[§2, Lemma 2.1 and Remark 2.2] The proof of §7 begins 'By Lemma 2.1, A∈S*_s(n)' for an arbitrary graph with ρ(A)+ρ(\bar A)≥ρ0. This requires the universal reading of Lemma 2.1: every extremal graph admits a staircase ordering. The manuscript's own Remark 2.2 states that Csikvári [5] showed the maximum is achieved by a graph with a staircase ordering and then asserts, without proof, that the maximum is attained only by such graphs. If only the existential reading holds, the argument in §§3–7 does not classify every extremal graph, and the final conclusion that G or its complement is complete split is not justified. The conjecture itself can still be recovered by applying the proof to an extremal representative in S*_s, but the quantifier in Lemma 2.1 and the wording of Remark 2.2 must be corrected or the universal statement proved.
[§3, Proposition 3.2] Proposition 3.2 is stated as ρ(A)<ρ(A1), but the proof shows only φ(A)<φ(A1) via (3.2). Because ρ(A)≤φ(A) and ρ(A1)≤φ(A1), the strict inequality for ρ does not follow from the displayed argument. The subsequent applications (after Figure 1 and in Lemma 3.3) use the φ comparison, so the proposition should be restated as φ(A)<φ(A1); if ρ(A)<ρ(A1) is intended, additional justification is needed.
[§6, Lemma 6.3 and §7] The derivation of (6.4) and the later use of the equality case of (5.1) in Proposition 6.5 silently assume equality in Lemma 5.1. Lemma 5.1 states only a sufficient condition for equality, and the matrices obtained after Lemma 3.4 satisfy v=n−\bar c rather than v=n−\bar c−1. The equality is true when c+\bar c≥n because then a_{c+1,n−\bar c}=1 and row c+1 has exactly n−\bar c ones, but this justification is omitted. Please add it explicitly, since Lemma 6.3 is the basis for the monotonicity of g(x) in Proposition 6.4.

minor comments (3)

[Throughout] Several typos should be corrected: 'suck' → 'such' in the proof of Lemma 2.9, 'shell' → 'shall' in the proof of Proposition 6.1, 'Morover' → 'Moreover' in Lemma 3.5, 'Disctrete' → 'Discrete' in reference [2], and 'Cambrigde' → 'Cambridge' in reference [9].
[§3, Lemma 3.5] The proof of Lemma 3.5 is much less detailed than that of Lemma 3.4; please specify the row and column moves used in the construction of A2 and the termination condition for the iterative process.
[§3, after (3.3)] The informal description of reading the complement parameters 'leftward from the a_{6,6} position' is hard to follow; a more systematic explanation of how to compute \bar c, \bar v, \bar s from A would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper-bound chain is derived from independent row-sum theorems, and the extremal equality is forced by their equality cases rather than by fitting the conjecture.

full rationale

The paper does not assume Conjecture 1.1. Section 3 defines the upper bound phi(A) from Theorem 2.3 (Liu-Weng and Duan-Zhou), and Section 5 bounds c+c-bar by a counting inequality; both are independent of the extremal value. The equality analysis in Lemma 4.1 uses the equality condition of Theorem 2.3 to characterize when rho(A)+rho(A-bar)=phi(A)+phi(A-bar), yielding complete split graphs. Section 7 combines these upper bounds, not any fitted parameter, so no prediction is forced by construction. The authors' own Theorem 2.5 (Cheng-Weng [4]) is used only in the final (3k+2,2k+1,2k+1) case as a published comparison theorem with stated hypotheses; it is not a self-citation chain replacing the proof, and it does not assume the target result. The one genuine caveat is Remark 2.2: the paper asserts, without proof, that Csikvari's argument shows the S*_s condition is 'essential' and that the maximum 'is attained only by such graphs,' whereas the quoted Lemma 2.1 as stated gives existence of an ordering for each extremal graph. If only the weaker existential reading is available, Section 7's opening 'By Lemma 2.1, A in S*_s(n)' for an arbitrary graph G is unsupported, and the classification of every extremal graph would not follow. That is a verification gap and correctness risk about the cited lemma, not a circular derivation: the theorem's conclusion is not equivalent to any of the paper's inputs, and no equation or fitted parameter is renamed as the answer.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The proof introduces no free parameters or invented entities. It relies on published structural and matrix-spectral theorems, two of which (Theorems 2.3 and 2.5) come from the same research group but are independently established results.

assumptions (4)

domain assumption Lemma 2.1 (Csikvári [5]): an extremal graph has a vertex ordering whose adjacency matrix lies in S*_s(n).
Invoked in Section 2 to restrict the search to staircase matrices. It is a published theorem and not proved in this paper.
standard math Theorem 2.3: ρ(A) ≤ φ_ℓ(A) for (0,1)-matrices with sorted row sums, from Liu-Weng [10] and Duan-Zhou [6].
Used to define the upper bound φ(A) in Section 3. External published bounds.
standard math Theorem 2.5: rooted-matrix bound of Cheng-Weng [4].
Used in the final case (Section 7) to bound ρ(\bar A) and ρ(A) via a 6x6 quotient matrix.
standard math Standard Perron-Frobenius and equitable partition lemmas (Lemmas 2.6, 2.7).
Used to simplify spectral radius computations for quotient matrices.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nordhaus-Gaddum inequality for the spectral radius of a graph of order $n$." pith.science (2026). https://pith.science/paper/CQC4JBPB

@misc{pith2026250611401,
  author       = {Pith},
  title        = {Pith review of: Nordhaus-Gaddum inequality for the spectral radius of a graph of order $n$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CQC4JBPB}},
  note         = {Machine review of arXiv:2506.11401}
}

abstract

We determine the extremal graph $G$ of order $n$ that maximizes the sum of the spectral radii of $G$ and its complement. This resolves a conjecture posed by Stevanovi\'{c} in 2007.

Figures

Figures reproduced from arXiv: 2506.11401 by the authors.

**Figure 2.** The matrices A, A2 with c(A) = c(A2) = 4 and ϕ(A) < ϕ(A2). Lemma 3.5. If A ∈ S ∗ (n) has parameters c = c(A), v = v(A), s = s(A), c = c(A), v = v(A), s = s(A) satisfying n − c < v and v = 2c − s, then there exists A2 ∈ S ∗ (n) whose parameters c2 = c(A2), v2 = v(A2), s2 = s(A2), c2 = c(A2), v2 = v(A2), s2 = s(A2) satisfy c2 = c, v2 = max{2c2 − s2, n − c}, s2 + v2 ≥ s + v, c2 = c, v2 = v, s2 = s. Morover, ϕ(A) ≤ ϕ(A2… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Generalized Nordhaus--Gaddum Inequalities for Eigenvalues
math.CO 2026-07 conditional novelty 7.0 of 10

The asymptotic maximum of λ₁(G)+λ₂(complement of G) is exactly 8/7 per vertex, with new general bounds for all pairs and a short proof of Terpai's spectral-radius bound.

Reference graph

Works this paper leans on

14 extracted references · 14 canonical work pages · cited by 1 Pith paper

[5]

Csikv´ ari, On a conjecture of V

P. Csikv´ ari, On a conjecture of V. Nikiforov,Discrete Math., 309 (2009), 4522–4526

work page 2009
[1]

Aouchiche, F

M. Aouchiche, F. K. Bell, D. Cvectovi´ c, P. Hansen, P. Rowlinson, S. Simi´ c, and D. Stevanovi´ c, Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph, Eur. J. Oper. Res., 191 (2008), 661–676

work page 2008
[2]

Aouchiche, P

M. Aouchiche, P. Hansen, A survey of Nordhaus-Gaddum type relations, Disctrete Appl. Math., 161 (2013), 466–546

work page 2013
[3]

A. E. Brouwer and W. H. Haemers,Spectral of graphs, Springer, 2012

work page 2012
[4]

Cheng and C.-w

Y.-J. Cheng and C.-w. Weng, A matrix realization of spectral bounds, J. Comb. Theory Ser. B, 174 (2025), 1–27

work page 2025
[6]

X. Duan, B. Zhou, Sharp bounds on the spectral radius of a nonnegative matrix,Linear Algebra Appl., 439 (2013), 2961–2970

work page 2013
[7]

C. D. Godsil,Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993

work page 1993
[8]

E. A. Nordhaus, J. Gaddum, On complementary graphs,Amer. Math. Monthly, 65 (1956), 175–177

work page 1956

Show all 14 references

[9]

R. A. Horn and C. R. Johnson,Topics in matrix analysis, Cambrigde University Press, 1991

1991
[10]

Liu and C.-W

C.-A. Liu and C.-W. Weng, Spectral radius and degree sequence of a graph,Linear Algebra Appl., 438 (2013), 3511–3515

2013
[11]

Liu, Graph limits and spectral extremal problems for graphs,SIAM J

L. Liu, Graph limits and spectral extremal problems for graphs,SIAM J. Discrete Math., 38 (2024), 10.1137/22M1508807

2024 doi
[12]

Nikiforov, Eigenvalue problems of Nordhaus-Gaddum type,Discrete Math., 307 (2007), 774–780

V. Nikiforov, Eigenvalue problems of Nordhaus-Gaddum type,Discrete Math., 307 (2007), 774–780

2007
[13]

Stevanovi´ c, Research problems from the Aveiro workshop on graph spectra,Linear Algebra Appl., 423 (2007), 172–181

D. Stevanovi´ c, Research problems from the Aveiro workshop on graph spectra,Linear Algebra Appl., 423 (2007), 172–181. 23

2007
[14]

Terpai, Proof of a conjecture of V

T. Terpai, Proof of a conjecture of V. Nikiforov,Combinatorica, 31 (2011), 739–754. 24

2011

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [5]

Csikv´ ari, On a conjecture of V

P. Csikv´ ari, On a conjecture of V. Nikiforov,Discrete Math., 309 (2009), 4522–4526

work page 2009

[2] [1]

Aouchiche, F

M. Aouchiche, F. K. Bell, D. Cvectovi´ c, P. Hansen, P. Rowlinson, S. Simi´ c, and D. Stevanovi´ c, Variable neighborhood search for extremal graphs. 16. Some conjectures related to the largest eigenvalue of a graph, Eur. J. Oper. Res., 191 (2008), 661–676

work page 2008

[3] [2]

Aouchiche, P

M. Aouchiche, P. Hansen, A survey of Nordhaus-Gaddum type relations, Disctrete Appl. Math., 161 (2013), 466–546

work page 2013

[4] [3]

A. E. Brouwer and W. H. Haemers,Spectral of graphs, Springer, 2012

work page 2012

[5] [4]

Cheng and C.-w

Y.-J. Cheng and C.-w. Weng, A matrix realization of spectral bounds, J. Comb. Theory Ser. B, 174 (2025), 1–27

work page 2025

[6] [6]

X. Duan, B. Zhou, Sharp bounds on the spectral radius of a nonnegative matrix,Linear Algebra Appl., 439 (2013), 2961–2970

work page 2013

[7] [7]

C. D. Godsil,Algebraic combinatorics, Chapman and Hall Mathematics Series, Chapman & Hall, New York, 1993

work page 1993

[8] [8]

E. A. Nordhaus, J. Gaddum, On complementary graphs,Amer. Math. Monthly, 65 (1956), 175–177

work page 1956