Nonregular graphs with a given maximum degree attaining maximum spectral radius

Chenxi Yang; Jiahui Liu; Zejun Huang

REVIEW 2 major objections 5 minor 17 references

Nonregular graphs with a given maximum degree attaining maximum spectral radius

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read For connected nonregular graphs with maximum degree $n-2$ or $n-3$, the paper identifies exactly which graphs maximize the spectral radius, confirming the degree-sequence conjecture in these cases.

desk verdict Genuine new characterizations for Δ=n-2 and Δ=n-3; Theorem 4 is very likely correct but the unshown 59≤n≤99 computer check needs to be supplied. read the letter →

arxiv 2411.17371 v1 pith:XIPNHITX submitted 2024-11-26 math.CO

Zejun Huang , Jiahui Liu , Chenxi Yang This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords spectralradiusnonregulargraphsmaximumdegreePerronvectorequitablepartitionquotientmatrixextremal

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

This paper settles, in two families of near-complete graphs, the question of which connected nonregular graph with $n$ vertices and maximum degree $\Delta$ has the largest spectral radius. When $\Delta=n-2$, it proves that every such extremal graph is one of two explicitly constructed block graphs, with the choice depending on whether $n$ is even or odd. When $\Delta=n-3$ and $n\ge 59$, it proves the extremal graph is unique: a specified graph $H_1(n)$ for even $n$ and $H_2(n)$ for odd $n$. These are the first complete structural characterizations for $\Delta$ this close to $n$, and they confirm the degree-sequence conjecture from 2008 in these cases. The proof confines the vertices of degree below $\Delta$ to a set of size one or two and then compares explicit characteristic polynomials.

What carries the argument

The workhorse is the Perron vector $x$ of the adjacency matrix, partitioned by $S$ (vertices with degree below $\Delta$) and $T$ (vertices with degree $\Delta$). A lemma cited from earlier work says that in an extremal graph, for deficient vertices $u,v$, $x_v\le x_u$ exactly when the $T$-neighbourhood of $v$ is contained in that of $u$; combined with completeness of $G[S]$, this forces $|S|=1$ for $\Delta=n-2$ and $|S|\in\{1,2\}$ for $\Delta=n-3$. Once the degree sequence is fixed, the graph is built from components whose complement is a union of paths and cycles, and edge-switching operations are used to show any configuration except the claimed ones can be improved. For the final comparison, the graphs carry equitable partitions whose quotient matrices have explicit characteristic polynomials (a cubic for $\Delta=n-2$ and quartics for $\Delta=n-3$); comparing their largest real roots selects the extremal graph.

What would settle it

Find a connected nonregular graph with $\Delta=n-3$ and $n\ge 59$ whose spectral radius exceeds that of $H_1(n)$ (even $n$) or $H_2(n)$ (odd $n$), or exhibit a counterexample to the cited monotonicity lemma: two deficient vertices $u,v$ with $x_v\le x_u$ but $N_T(v)$ not contained in $N_T(u)$. For the claimed threshold, a symbolic verification of the sign pattern (15) for all $59\le n\le 99$ would test the only computer-assisted step.

Watch

Extended reading notes

Core claim

The paper's central discovery is a complete classification of the spectral-radius-extremal connected nonregular graphs when the maximum degree is $n-2$ or $n-3$. Theorem 3 states that for $n\ge 5$, a graph in $\mathcal{G}(n,n-2)$ is isomorphic to $G(n,n-3)$ when $n$ is odd, and to $G(n,n-4)$ or $G(n,2)$ when $n$ is even, where $G(n,t)$ is the graph built from a vertex $u$ joined to $K_t$ with a perfect matching removed, that graph joined completely to $K_{n-t-1}$. Theorem 4 states that for $n\ge 59$, a graph in $\mathcal{G}(n,n-3)$ is isomorphic to $H_1(n)$ for even $n$ and $H_2(n)$ for odd $n$. Thus the extremal graph for $\Delta=n-3$ is unique and has degree sequence $(\Delta,\ldots,\Delta,1)$ for even $n$ and $(\Delta,\ldots,\Delta,2)$ for odd $n$, the smallest minimum degree allowed by parity.

Load-bearing premise

The load-bearing premise is a lemma cited from earlier work, not proved here, asserting that in any extremal graph, comparing Perron-vector entries of two deficient vertices is the same as comparing containment of their neighbourhoods inside the full-degree set; the structural reductions that shrink $S$ to size one or two all hang on it.

Editorial extensions

If this is right

For $\Delta=n-3$ and $n\ge 59$, spectral-radius maximization has a unique solution: $H_1(n)$ for even $n$, $H_2(n)$ for odd $n$; every other connected nonregular graph with the same order and maximum degree has strictly smaller spectral radius.
For $\Delta=n-2$ and $n\ge 5$, the extremal graphs are exactly the three explicit families $G(n,n-3)$, $G(n,n-4)$, and $G(n,2)$, with the choice fixed by parity.
The extremal graph for $\Delta=n-3$ has minimum degree $1$ (even $n$) or $2$ (odd $n$), the smallest positive value allowed by parity, so in these regimes the gap $\Delta-\rho(G)$ is as large as the structure permits.
The spectral radius of the extremal graph is the largest real root of one of the explicit characteristic polynomials derived from quotient matrices, giving a direct numerical route to the gap $\Delta-\lambda_1(n,\Delta)$ for these $\Delta$.

Reading between the lines

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

If the same quotient-matrix pattern persists for $\Delta=n-c$ with fixed $c$, one would expect a similar parity-driven dichotomy: unique extremal graphs for odd $n$ and a small finite list for even $n$, with minimum degree $1$ or $2$; this is an extension the paper does not state.
The $n\ge 59$ threshold rests on a finite computer check of the sign pattern (15) for $59\le n\le 99$; making that interval check fully symbolic or publishing the verification table would remove the only non-human step from the proof.
The quantitative inequalities in (9)--(11) could support a stability version of Theorem 4: any graph whose spectral radius is within $\varepsilon$ of the maximal value should have small $S$ and complement structure close to $H_1(n)$ or $H_2(n)$.

Share X Bluesky LinkedIn Reddit HN

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

The two characterizations are real results. Theorem 3 is clean and complete as far as I checked; Theorem 4 is the substantive one, and the proof strategy—reduce to |S|≤2, then compare quotient polynomials—is the right inheritance from Liu's program. The paper does what it claims: for Δ=n-2 and Δ=n-3 it pins down the extremal graphs exactly, and the n−3 case was open. Credit where due: the authors do not fit parameters; extremal candidates are constructed first and shown optimal by polynomial comparison.

The soft spots are concrete but not fatal. The biggest is the n=59..99 range in Theorem 4. The sign pattern (15) is asserted to hold by "direct computation (which we check by computers)", but no code, output table, or exact arithmetic is provided. Since the theorem threshold is n≥59, the whole conclusion for that range depends on that unshown check. This is not a disagreement with consensus; it is a verification gap. The fix is easy: supply machine-checkable or tabulated verification, or extend the analytic estimates downward.

Second, the H2(n) definition in Section 1 is internally inconsistent: it says |V2|=|V3|=2 and then writes H2[V3]=K_{n-7}-M_{(n-7)/2}. The proof's G2^(2) makes the intended partition clear enough (the large set is T''), so this is a typo-level defect, but it will confuse a reader and must be fixed. Same for the determinant display in Section 3, which uses a row operation that is not valid as written even though the final polynomial is correct.

Third, Lemma 6 from Liu 2024 is load-bearing for both structural reductions. It is a published result, not a self-citation problem, but the paper treats it as background and does not flag how much of Theorems 3 and 4 depends on it. A one-sentence dependency statement would be appropriate.

My bottom line: the central argument holds up in outline, the results are new, and I found no sign of cooked data or circular fitting. The paper deserves a serious referee. I would ask the authors to close the finite-check gap and clean up the typos before acceptance, but this should not be desk-rejected.

Who benefits: people working on spectral extremal graph theory, especially the Liu–Li conjecture. I would take it to reading group and would cite it once the finite check is resolved.

Referee Report

2 major / 5 minor

Summary. The paper considers connected nonregular graphs of order n and maximum degree Δ that attain the maximum spectral radius, denoted G(n,Δ). It proves two structural characterizations: Theorem 3 states that for Δ=n−2 and n≥5 the extremal graphs are exactly G(n,n−3) for odd n and either G(n,n−4) or G(n,2) for even n; Theorem 4 states that for Δ=n−3 and n≥59 the extremal graph is unique, isomorphic to H1(n) for even n and to H2(n) for odd n. The proof reduces the possible degree sequences using Perron-vector monotonicity (Lemma 6), then compares characteristic polynomials of equitable quotient matrices after a series of local switching operations. The final comparison in the Δ=n−3 case is reduced to root ordering of three quartics f1, f2, and g.

Significance. If the proof is completed, the paper gives the first complete extremal-graph characterizations for maximum degree within a constant of the order, and it confirms the Liu–Li and Liu conjectures in these two families. The candidate graphs are explicit and simple, the quotient-matrix computations are deterministic, and the main root comparisons are checkable by hand for n≥100. I found no circularity: the external Lemma 6 is cited from Liu's published work, and the polynomial comparisons are not fitted to the conclusion. The main obstacle to accepting Theorem 4 as proved is the unverified computer-assisted range 59≤n≤99; a second obstacle is that the definition of H2(n) in Section 1 is internally inconsistent. These issues are local and repairable, but they currently prevent the proof from being fully checkable.

major comments (2)

[Section 4, inequality (15)] The proof of Theorem 4 for 59≤n≤99 depends entirely on the assertion that g(t4)<0, g(t3)>0, g(t2)<0, g(t1)>0, stated as 'a direct computation (which we check by computers)'. No code, output table, or exact arithmetic certificate is provided. Since the threshold of Theorem 4 is n≥59 and the sign pattern is used to locate the roots of g and to conclude ρ(f2)>ρ(g) (or ρ(f1)>ρ(g)), an error in any of these signs for some n in this range would invalidate the extremal characterization. Please supply a verifiable computation for the finitely many n (for example, exact rational arithmetic or Sturm-sequence certificates for the polynomials t↦g(t_i(n))), or extend the analytic estimates down to n=59.
[Section 1, definition of H2(n)] As written, the bullet list defining H2(n) is inconsistent: it declares |V2|=|V3|=2 while also requiring H2[V3]=K_{n−7}−M_{(n−7)/2}, which is impossible for n≥59. The figure and the proof in Subcase 1.2.2 indicate that V1 and V2 are the two two-vertex sets and V3 is the large set. Please correct the partition data (e.g., |V1|=|V2|=2, H2[V1∪V2]=K4, and H2[V3]=K_{n−7}−M_{(n−7)/2}) and adjust the adjacency bullets accordingly. As it stands, Theorem 4 refers to a graph that is not defined.

minor comments (5)

[Section 3, determinant display] The equality between the first 3×3 determinant and the second is not obtained by a valid row operation. The final polynomial f(δ,λ) is correct, but the displayed transformation should be replaced by a valid computation or an algebraic simplification.
[Section 4, Subcase 2.1, n-even comparison] The displayed simplification '3n²−22n+38' after the lower bound appears to be an algebra slip; the expression evaluates to n²−8n+14. The positivity conclusion is unaffected for n≥59, but the display should be corrected.
[Section 2, proof of Lemma 16] The statement 'Y^T(dI−J_{n−3})Y≥0' should read 'dI−J_d', since Y has dimension d.
[Section 2, before Lemma 12] 'Similarly as Lemma 12' should refer to Lemma 11.
[Section 1, notation] The notation G(n,t) for the auxiliary graph collides with the notation G(n,Δ) for the extremal family; consider using a different symbol for the auxiliary graph.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the extremal candidates are constructed independently and then compared via characteristic polynomials, not fitted to the target result.

full rationale

The paper's derivation chain is self-contained and non-circular. It assumes G is in G(n, Delta), uses external structural lemmas (Lemmas 5-7, cited from Liu 2024 and earlier work) to restrict the set S of non-maximum-degree vertices, then explicitly constructs the candidate graphs G(n,t), H1(n), and H2(n). These candidates are defined independently of any spectral radius data, and their optimality is established by comparing characteristic polynomials of equitable quotient matrices (e.g., f1, f2, g in Theorem 4) rather than by tuning a parameter to force the desired conclusion. No fitted parameter is renamed as a prediction: the degree sequence restrictions follow from structural arguments, and the comparisons of the largest roots are analytic or finite computations. The computational verification behind inequality (15) for 59 <= n <= 99 is a proof gap or reproducibility concern, not circularity, because it does not substitute the theorem's conclusion for an input. The cited lemmas from Liu 2024 are external published results with independent content; even if one author overlaps with the present paper, the lemmas are not the theorem being proved and are used as hypotheses, so they do not make the argument circular. The apparent typo in the definition of H2(n) (saying |V3|=2 while writing H2[V3]=K_{n-7}-M_{(n-7)/2}) is an internal correctness issue, not a circularity issue. Overall, the derivation does not reduce to its own inputs.

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

The proof leans on five prior lemmas, all standard or recent published results in the same line of work; no free parameters are fitted and no new entities are postulated. The main unverified input is the finite computer check in Section 4.

assumptions (5)

standard math Lemma 5 ([11]): for G ∈ G(n, Δ), the subgraph induced by deficient vertices S is complete.
Used in Theorem 3 and Case 2 to compute d(u) = |T| + |S| - 1, forcing |S|=1 or 2.
standard math Lemma 6 ([8]): for u, v ∈ S, x_v ≤ x_u iff N_T(v) ⊆ N_T(u).
Central external monotonicity result used to localize the maximum Perron entry in S to a vertex adjacent to all of T; not proved in this paper.
standard math Lemma 7 ([8]): any deficient vertex has strictly smaller Perron entry than any full-degree vertex.
Used in Subcase 1.2 to rule out x1=x5 and in Case 2 to order x_u < x_t for t ∈ T.
standard math Quotient matrix and Perron-Frobenius facts (Lemmas 9, 10, 14, 15).
Let the paper replace the spectral radius of a graph by the spectral radius of an equitable quotient matrix; standard.
standard math Handshaking parity determines possible δ values.
Used to restrict δ to even or odd values in the case analysis.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nonregular graphs with a given maximum degree attaining maximum spectral radius." pith.science (2026). https://pith.science/paper/XIPNHITX

@misc{pith2026241117371,
  author       = {Pith},
  title        = {Pith review of: Nonregular graphs with a given maximum degree attaining maximum spectral radius},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XIPNHITX}},
  note         = {Machine review of arXiv:2411.17371}
}

abstract

Let $G$ be a connected nonregular graphs of order $n$ with maximum degree $\Delta$ that attains the maximum spectral radius. Liu and Li (2008) proposed a conjecture stating that $G$ has a degree sequence $(\Delta,\ldots,\Delta,\delta)$ with $\delta<\Delta$. For $\Delta=3$ and $\Delta=4$, Liu (2024) confirmed this conjecture by characterizing the structure of such graphs. Liu also proposed a modified version of the conjecture for fixed $\Delta$ and sufficiently large $n$, stating that the above $\delta=\Delta-1$ if $\Delta$ and $n$ are both odd, $\delta=1$ if $\Delta$ is odd and $n$ is even, and $\delta=\Delta-2$ if $\Delta$ is even. For the cases where $\Delta=n-2$ with $n\ge 5$, and $\Delta=n-3$ with $n\ge 59$, we fully characterize the structure of $G$.

Figures

Figures reproduced from arXiv: 2411.17371 by the authors.

**Figure 2.** G(n, δ) Notice that π = {{u}, T1, T2} is an equitable partition of V (G) with quotient matrix Aδ =   0 δ 0 1 δ − 2 n − δ − 1 0 δ n − δ − 2   , whose characteristic polynomial is det(λI − Aδ) = [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

**Figure 3.** G1, where G[T ′ ] = Kn−4 − Mn−4 2 Since n ≥ 59, we have T ′ 6= ∅. Therefore, π = {{u}, {v1}, {v2, v3}, T′} is an equitable partition of V (G1) with quotient matrix B1 =   0 1 0 0 1 0 0 n − 4 0 0 1 n − 4 0 1 2 n − 6   , whose characteristic polynomial is P(B1, λ) = λ 4 + (5 − n)λ 3 + (5 − 2n)λ 2 + (2n − 9)λ + n − 2 ≡ f1(λ). (1) Moreover, ρ(G) = ρ(G1) = ρ(B1) is the maximum real eigenvalue of B1, as B1 is … view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: G (1) 2 , G(2) 2 Subcase 1.2.2. v1v2 ∈ E(G). Suppose V (G) − N[v1] = {v3, v5}, V (G) − N[v2] = {v4, v6}. Then N[v3] = N[v5] = V (G) \ {u, v1}, N[v4] = N[v6] = V (G) \ {u, v2}. Let T ′′ = V (G) \ {u, vi , i = 1, 2, · · · , 6}. Since u 6∈ N(v) and {v1, v2, v3, v4, v5, v6…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

N. Alon, B. Sudakov, Bipartite subgraphs and the smallest eigenv alue, Comb. Probab. Comput. 9 (1) (2000) 1-12

work page 2000
[2]

X. Chen, Y. Hou, The extreme eigenvalues and maximum degree of k-connected irregular graphs, Linear Algebra Appl. 463 (2014) 33-44

work page 2014
[3]

Cioabˇ a, The spectral radius and the maximum degree of irre gular graphs, Elec- tron

S.M. Cioabˇ a, The spectral radius and the maximum degree of irre gular graphs, Elec- tron. J. Comb. 14 (2007) R38

work page 2007
[4]

Cioabˇ a, D.A

S.M. Cioabˇ a, D.A. Gregory, V. Nikiforov, Extreme eigenvalues of nonregular graphs, J. Combin. Theory Ser. B 97 (2007) 483-486

work page 2007
[5]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c, An Introduction to theTheory of Graph Spec- tra, Cambridge University Press, 2009

work page 2009
[6]

R. Feng, W. Zhang, A note on spectral radius and maximum degre e of irregular graphs, Graphs Comb. 37 (2021) 1121-1127

work page 2021
[7]

Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl

W. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226-228 (1995) 593-616

work page 1995
[8]

Liu, Extremal spectral radius of nonregular graphs with pre scribed maximum degree, J

L. Liu, Extremal spectral radius of nonregular graphs with pre scribed maximum degree, J. Combin. Theory Ser. B 169 (2024) 430-479

work page 2024

Show all 17 references

[9]

B. Liu, Y. Huang, Z. You, On λ 1-extremal non-regular graphs, Electron. J. Linear Algebra 18 (2009) 735-744

2009
[10]

B. Liu, G. Li, A note on the largest eigenvalue of non-regular gra phs, Electron. J. Linear Algebra 17 (2008) 54-61

2008
[11]

B. Liu, M. Liu, Z. You, Erratum to ‘A note on the largest eigenvalu e of non-regular graphs’, Electron. J. Linear Algebra 18 (2009) 64-68. 27

2009
[12]

B. Liu, J. Shen, X. Wang, On the largest eigenvalue of non-regu lar graphs, J. Combin. Theory Ser. B 97 (2007) 1010-1018

2007
[13]

Stevanovi´ c, The largest eigenvalue of nonregular graphs , J

D. Stevanovi´ c, The largest eigenvalue of nonregular graphs , J. Combin. Theory Ser. B 91 (2004) 143-146

2004
[14]

J. Xue, R. Liu, J. Guo, J. Shu, The maximum spectral radius of ir regular bipartite graphs, Adv. Appl. Math. 142 (2023) paper 102433

2023
[15]

Zhan, Matrix Theory, Graduate Studies in Mathematics, vol

X. Zhan, Matrix Theory, Graduate Studies in Mathematics, vol. 147, American Math- ematical Society, Providence, RI, 2013

2013
[16]

Zhang, A new result on spectral radius and maximum degree o f irregular graphs, Graphs Comb

W. Zhang, A new result on spectral radius and maximum degree o f irregular graphs, Graphs Comb. 37 (2021) 1103-1119

2021
[17]

Zhang, Eigenvectors and eigenvalues of nonregular graphs , Linear Algebra Appl

X. Zhang, Eigenvectors and eigenvalues of nonregular graphs , Linear Algebra Appl. 409 (2005) 79-86. 28

2005

Pith tools

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

[1] [1]

N. Alon, B. Sudakov, Bipartite subgraphs and the smallest eigenv alue, Comb. Probab. Comput. 9 (1) (2000) 1-12

work page 2000

[2] [2]

X. Chen, Y. Hou, The extreme eigenvalues and maximum degree of k-connected irregular graphs, Linear Algebra Appl. 463 (2014) 33-44

work page 2014

[3] [3]

Cioabˇ a, The spectral radius and the maximum degree of irre gular graphs, Elec- tron

S.M. Cioabˇ a, The spectral radius and the maximum degree of irre gular graphs, Elec- tron. J. Comb. 14 (2007) R38

work page 2007

[4] [4]

Cioabˇ a, D.A

S.M. Cioabˇ a, D.A. Gregory, V. Nikiforov, Extreme eigenvalues of nonregular graphs, J. Combin. Theory Ser. B 97 (2007) 483-486

work page 2007

[5] [5]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c, An Introduction to theTheory of Graph Spec- tra, Cambridge University Press, 2009

work page 2009

[6] [6]

R. Feng, W. Zhang, A note on spectral radius and maximum degre e of irregular graphs, Graphs Comb. 37 (2021) 1121-1127

work page 2021

[7] [7]

Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl

W. Haemers, Interlacing eigenvalues and graphs, Linear Algebra Appl. 226-228 (1995) 593-616

work page 1995

[8] [8]

Liu, Extremal spectral radius of nonregular graphs with pre scribed maximum degree, J

L. Liu, Extremal spectral radius of nonregular graphs with pre scribed maximum degree, J. Combin. Theory Ser. B 169 (2024) 430-479

work page 2024