The general spectral radius and majorization theorem of $t$-cone graphs with given degree sequences

Muhuo Liu; Yufei Huang

REVIEW 2 major objections 3 minor 20 references

The general spectral radius and majorization theorem of $t$-cone graphs with given degree sequences

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

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

Pith's one-line read This paper proves that for t-cone trees, unicyclic graphs, and bicyclic graphs with a prescribed degree sequence, the unique graph maximizing the general spectral radius is the layered BFS-join graph, and that majorization between degree…

desk verdict A solid completion of the extremal characterization for t-cone graphs under the general spectral radius; the one flagged gap in Theorem 3.1 is a presentation issue, not a real flaw. read the letter →

arxiv 1908.06224 v1 pith:67KODJQ7 submitted 2019-08-17 math.CO

Yufei Huang , Muhuo Liu This is my paper · ORCID

classification math.CO MSC 05C5015A18

keywords generalspectralradiusTheta_alpha-maximalgrapht-conec-cyclicdegreesequencemajorizationBFS-graph

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 studies the general spectral radius Θ(G,α), the largest eigenvalue of A(G)+αD(G), restricted to t-cone c-cyclic graphs—joins of a complete graph K_t with a tree, unicyclic, or bicyclic graph—whose degree sequence is fixed. It establishes that within each such class the unique maximizer is a specific breadth-first-search-type graph: the join of K_t with the BFS-tree (or its unicyclic/bicyclic analogue), for c=0,1,2. It then proves a majorization monotonicity law: if one degree sequence strictly majorizes another, the extremal general spectral radius of the former is strictly smaller, for trees and unicyclic graphs, and for bicyclic graphs outside one explicitly excluded family. A sympathetic reader would care because this unifies and extends a long line of extremal spectral results and gives a complete, constructive answer for these graph classes.

What carries the argument

The central machinery is the good t-cone BFS-ordering, an ordering of the non-cone vertices that layers them by distance from the first such vertex and orders neighbors within each layer by Perron-vector weight, together with the graph operations of shifting (moving a neighbor from a lower-weight vertex to a higher-weight vertex) and switching (exchanging two edges), which strictly increase Θ(G,α) under suitable Perron-vector inequalities. These tools force every Θ_α-maximal graph to be a good t-cone BFS-graph, whose structure is then shown to be unique for c=0,1,2. The majorization step uses the classical fact that strict majorization between integer sequences decomposes into unit transformations, each of which is realized locally by a shifting operation that raises the general spectral radius.

What would settle it

Build a small t-cone tree or unicyclic graph with a fixed degree sequence, compute Θ(G,α) numerically for several α, and compare it to the value for the BFS-join graph $T_π^{{(t)}}$ or $U_π^{{(t)}}$; finding any graph in Γ(π,t;c) with larger general spectral radius would refute Theorems 4.1 and 4.2. Alternatively, search for two degree sequences π ⊲ π′ of t-cone unicyclic graphs where the computed extremal radii satisfy Θ(G_π,α) ≥ Θ(G_π′,α), which would disprove Theorem 5.2; for c=2, the excluded family in Theorem 5.3 is the natural place to test whether the strict inequality genuinely fails there.

Watch

Extended reading notes

Core claim

For a fixed non-increasing degree sequence π of a t-cone c-cyclic graph, the unique Θ_α-maximal graph of Γ(π,t;c) is the layered BFS-join graph: $T_π^{{(t)}}$ = K_t ∨ T_{π*} for c=0, $U_π^{{(t)}}$ = K_t ∨ U_{π*} for c=1, and $B_π^{{(t)}}$ = K_t ∨ B_{π*} for c=2, where T_{π*}, U_{π*}, B_{π*} are the BFS-tree, BFS-unicyclic, and BFS-bicyclic graphs realizing the reduced degree sequence π*. Consequently, if π ⊲ π′ are degree sequences of t-cone trees or t-cone unicyclic graphs, then Θ(G_π,α) < Θ(G_π′,α), where G_π and G_π′ are the corresponding Θ_α-maximal graphs; for bicyclic graphs the same strict inequality holds except for a stated family of star-majorizations where the proof's surprising-vertex argument fails.

Load-bearing premise

The proof that every Θ_α-maximal graph is a good t-cone BFS-graph relies on the assertion, stated without proof in the proof of Theorem 3.1, that the graph H′ obtained by a two-edge switch remains connected whenever the involved vertices lie in the designated BFS levels; if a disconnected H′ were possible in that situation, the structural characterization and all subsequent uniqueness and majorization conclusions would lose their foundation.

Editorial extensions

If this is right

For any degree sequence of a t-cone tree, unicyclic graph, or bicyclic graph, the extremal graph for the general spectral radius is explicitly constructible by a breadth-first layering rule, so no search or optimization is needed once the degree sequence is known.
The strict monotonicity Θ(G_π,α) < Θ(G_π′,α) whenever π ⊲ π′ gives a clean ordering principle: more balanced degree sequences yield larger extremal general spectral radius for t-cone trees and unicyclic graphs.
Setting α=0 recovers the spectral-radius versions and α=1 the signless-Laplacian versions of these extremal and majorization results, so the paper's theorems simultaneously generalize earlier tree, unicyclic, and bicyclic results.
The bicyclic case c=2 is almost covered, with a single explicit family of star-majorizations left open; for all other majorizing steps the strict inequality holds.
Because the BFS-join graphs are unique maximizers, the paper yields exact comparison tools for any pair of degree sequences connected by a chain of unit transformations.

Reading between the lines

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

The excluded bicyclic family in Theorem 5.3 likely marks a genuine boundary where the surprising-vertex condition fails, suggesting that the monotonicity law for c=2 may need a different argument or may fail for those specific degree sequences.
The same BFS-join construction and majorization argument could plausibly extend to t-cone c-cyclic graphs for c≥3 for those degree sequences where a surprising vertex always exists, though known counterexamples for ordinary 3-cyclic and 4-cyclic graphs indicate the law cannot hold universally.
The characterization of Θ_α-maximal graphs is independent of the value of α≥0, so the extremal graph is universal across the entire family of general spectral radii; this suggests that the parameter α does not change the qualitative extremal structure for these classes.
A testable extension would be to ask whether the 'at most one surprising vertex' obstruction can be characterized combinatorially in terms of the degree sequence alone, which would make the c=2 boundary precise.

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

This is a good, honest paper that closes a line of inquiry. It gives the unique Θ_α-maximal graph for t-cone trees, unicyclic graphs, and bicyclic graphs with prescribed degree sequences, for every α ≥ 0, and proves the expected strict majorization result for c = 0, 1, with a clearly flagged conditional result for c = 2. That is genuinely new: previous work mostly covered the adjacency and signless Laplacian cases or single-cone graphs, and the t-cone bicyclic characterization appears to be new. The proof strategy is established — reduce to a good BFS-graph, then apply shifting and switching — but the c = 2 case involves enough casework that the paper earns its length. I also appreciate that the authors explicitly note the missing condition in their own book; that is the kind of transparency I like.

The main soft spot is exactly what the reader flagged: in Theorem 3.1, the statement "It can be checked that H′ is connected" is doing real work, because Corollary 2.2 depends on it. The stress-test argument shows the concern does not land: a shortest path from the root to u or x cannot use the edges uv or xy (either edge would force a detour through level L+1), so deleting those edges leaves u and x connected to the root, and the new edges xv and uy reattach v and y. But the paper should write that out; a one-sentence proof would remove the only genuine rigor gap I see.

Minor notes: the reliance on the authors' own book for the shifting/rewiring lemmas is acceptable, since those lemmas are standard and independently known, but a referee might want the statements cross-checked. The c = 2 majorization theorem explicitly excludes one family, and the paper only claims a conditional result there; that is honest and not a defect.

Bottom line: if I worked in extremal spectral graph theory, I would cite this. It is not revolutionary, but it is careful and it completes a natural program. I would send it to a competent referee, with the request to check the c = 2 case analysis carefully plus the connectivity argument in Theorem 3.1. My own expectation is that both survive scrutiny.

Referee Report

2 major / 3 minor

Summary. The paper studies the general spectral radius Θ(G,α)=λ_max(A(G)+αD(G)) on t-cone c-cyclic graphs K_t ∨ H with a fixed non-increasing degree sequence π. It proves that every Θ_α-maximal graph in Γ(π,t;c) is a "good t-cone BFS-graph" (Section 3). It then characterizes the unique maximal graph for c=0 as K_t ∨ T_{π*}, where T_{π*} is the BFS-tree with degree sequence π*; for c=1 as K_t ∨ U_{π*}; and for c=2 as one of four explicitly constructed graphs K_t ∨ B_{π*} depending on the form of π (Theorems 4.1–4.3). Finally, it proves strict monotonicity under majorization: if π ⊲ π′, then Θ(G_π,α) < Θ(G_{π′},α) for c=0,1, and for c=2 for star majorizations outside one explicitly excluded family (Theorems 5.1–5.3). The final section derives known single-cone and classical results as corollaries.

Significance. If the main claims are correct, the paper gives a uniform α-parametrized extension of known majorization results for trees, unicyclic graphs and bicyclic graphs, as well as for single-cone graphs, with explicit uniqueness characterizations. The BFS constructions are concrete, and the corollaries recovering earlier theorems are valuable. The proof framework is standard, relying on Perron–Frobenius theory and shifting/switching operations. Two points in the written proof need attention before the paper is fully rigorous: the reduction from general majorization to star majorization in Remark 5.1, and the connectivity assertion in Theorem 3.1. Both appear fixable, but the first is load-bearing for the majorization theorems.

major comments (2)

[§5, Remark 5.1] The reduction from an arbitrary majorization π ⊲ π′ to a chain of star majorizations is not established. Lemma 5.1 (from Marshall and Olkin) guarantees a sequence of unit transformations between integer sequences, but it does not guarantee that each intermediate sequence is non-increasing, graphical, or a degree sequence of a t-cone c-cyclic graph. Since Theorems 5.1–5.3 prove only the star-majorization step, the general statements for c=0,1 (and the qualified c=2 statement) require an additional lemma or citation showing that the chain can be chosen with every π_i in the relevant class Γ(π_i,t;c). Please supply this proof or a precise reference that covers t-cone c-cyclic degree sequences.
[§3, Theorem 3.1] Theorem 3.1 asserts "It can be checked that H′ is connected" before invoking Corollary 2.2, and this connectivity is essential for Definition 2.2(iii) and hence for all subsequent uniqueness theorems. The assertion is true under the level hypotheses: for a root r with h_H(u)=h_H(x)=L and h_H(v)=h_H(y)=L+1, a shortest r–u or r–x path cannot use uv or xy, so u and x remain connected to r after deleting those edges, and the added edges xv and uy reattach v and y. A written proof should replace the one-line assertion.

minor comments (3)

[§3, Lemma 3.1, Case 1] The phrase "In this case, G1 = Gπ" appears to be a typo; the graph G1 differs from Gπ. It should say that G1 has the same degree sequence as Gπ and lies in Γ(π,t;c), or that G1 ≠ Gπ.
[§5, Theorem 5.3, Case 3, Subcase 3.2] In Subcase 3.2, the sentence "Obviously, G1 ∈ B(π′,t)" should refer to G7, not G1.
[Abstract and §5] The c=2 result is described as a "similar result," but Theorem 5.3 is explicitly restricted to star majorizations and carries an excluded family. The abstract could state this qualification more precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main theorems are derived from external spectral-perturbation lemmas, independent BFS-tree uniqueness, and structural arguments, not from their own conclusions.

full rationale

The paper's target results are the characterization of the unique Θ_α-maximal t-cone graphs for c=0,1,2 and the majorization monotonicity theorems. Walking the derivation chain: the starting tools are standard Perron-Frobenius/Rayleigh-Ritz facts and the shifting/switching lemmas stated as Theorems 2.1 and 2.2 and credited to [12]. Although [12] is co-authored by the present author M. Liu, these lemmas are external, parameter-free, and do not assume the t-cone maximality under investigation; they are independently checkable spectral perturbation statements. The paper even flags a missing condition in [12, Remark 3.2.2], which is inconsistent with blind self-citation and supports independent assessment. Lemma 3.1 and Theorem 3.1 show that a Θ_α-maximal graph must be a good t-cone BFS-graph; Definition 2.2 is a structural characterization in terms of Perron weights, not a disguised version of the desired uniqueness, and Theorem 3.1 derives it from maximality via Corollary 2.2. The one abbreviated step, 'It can be checked that H′ is connected' in Theorem 3.1, is a rigor gap rather than circularity: connectivity under the level conditions is a graph-theoretic fact independent of the target theorem. The uniqueness of the BFS-tree T_{π*} is imported from Zhang [18], an external result whose assumptions do not include the present claims; the unicyclic and bicyclic uniqueness statements are proven structurally (Proposition 4.2, and Proposition 4.3 by analogy), not by assuming the extremal characterization. The majorization theorems then use Lemma 5.1 on unit transformations, Lemma 5.2, and the explicit existence of 'surprising vertices'; the c=2 exception is stated rather than hidden. No fitted parameters are promoted to predictions, and no displayed equation is equivalent to its input by construction. The abbreviated Proposition 4.3 and the unproved connectivity check are completeness issues, not circularity. Overall the derivation is self-contained apart from legitimate external lemmas, so the circularity score is 0.

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

No free parameters are introduced; α is a fixed non-negative input, and the degree sequence π is given. The paper relies on standard matrix theory, the shifting/switching lemmas of [12] (co-authored by one of the present authors), and the uniqueness of BFS-trees from [18]. The constructions of U_{π*} and B_{π*} are algorithmic but their existence is asserted.

assumptions (6)

standard math Perron-Frobenius theorem for nonnegative irreducible matrices
Used in Section 2 to guarantee a unique positive Perron vector for M_α(G) and monotonicity under subgraphs.
standard math Rayleigh-Ritz variational characterization of eigenvalues
Used in Section 2 (Rayleigh quotient) and in Lemma 3.2 to bound Θ(G,α) from below.
domain assumption Shifting operation inequality (Theorem 2.1) and switching inequality (Theorem 2.2) from [12]
The central tool for all extremal comparisons; these are standard results in the field, quoted from a book co-authored by one of the present authors.
domain assumption Uniqueness of the BFS-tree with a prescribed tree degree sequence (Zhang [18])
Used in Theorem 4.1 and Proposition 4.2 to identify the unique Θ_α-maximal tree and unicyclic structures.
standard math Marshall-Olkin majorization decomposition lemma (Lemma 5.1)
Used in Remark 5.1 to reduce general majorization to a chain of unit transformations (star majorizations).
domain assumption Degree-sequence feasibility conditions for t-cone c-cyclic graphs (Proposition 4.1)
The classification into cases (4.0.1), (4.1.1)-(4.1.2), and (4.2.1)-(4.2.4) is assumed throughout the uniqueness and majorization proofs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of The general spectral radius and majorization theorem of $t$-cone graphs with given degree sequences." pith.science (2026). https://pith.science/paper/67KODJQ7

@misc{pith2026190806224,
  author       = {Pith},
  title        = {Pith review of: The general spectral radius and majorization theorem of $t$-cone graphs with given degree sequences},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/67KODJQ7}},
  note         = {Machine review of arXiv:1908.06224}
}

abstract

The general spectral radius of a graph $G$, denoted by $\Theta(G,\alpha)$, is the maximal eigenvalue of $M_{\alpha}(G)=A(G)+\alpha D(G)$ $(\alpha\geq 0)$, where $A(G)$ and $D(G)$ are the adjacency matrix and the diagonal matrix of vertex degrees of $G$, respectively. A graph $G$ is called $\Theta_\alpha$-maximal in a class of connected simple graphs $\mathcal {G}$ if $\Theta(G,\alpha)$ is maximal among all graphs of $\mathcal {G}$. A $t$-cone $c$-cyclic graph is the join of a complete graph $K_t$ and a $c$-cyclic connected simple graph. Let $\pi=\big(d_1,d_2,\ldots,d_n\big)$ and $\pi'=\big(d'_1,d'_2,\ldots,d'_n\big)$ be two non-increasing degree sequences of $t$-cone $c$-cyclic graphs with $n$ vertices. We say $\pi$ is strictly majorized by $\pi'$, denoted by $\pi \lhd \pi'$, if $\pi\neq \pi'$, $\sum_{i=1}^n d_i=\sum_{i=1}^n d_i'$, and $\sum_{i=1}^k d_i\leq \sum_{i=1}^k d_i'$ for $k=1,2,\ldots,n-1$. Denote by $\Gamma(\pi,t;c)$ the class of $t$-cone $c$-cyclic graphs with $\pi$ as its degree sequence. In this paper, we determine some properties of $\Theta_\alpha$-maximal graphs of $\Gamma(\pi,t;c)$ and characterize the unique $\Theta_\alpha$-maximal graph of $\Gamma(\pi,t;0)$ \big(resp. $\Gamma(\pi,t;1)$ and $\Gamma(\pi,t;2)$\big). Moreover, we prove that if $\pi \lhd \pi'$, $G$ and $G'$ are the $\Theta_\alpha$-maximal graphs of $\Gamma(\pi,t;c)$ and $\Gamma(\pi',t;c)$ respectively, then $\Theta(G,\alpha)<\Theta(G',\alpha)$ for $c\in \big\{0,1\big\}$, and we also consider the similar result for $c=2$.

Figures

Figures reproduced from arXiv: 1908.06224 by the authors.

**Figure 4.** [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗

**Figure 4.** [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages

[1]

Belardo, E.M

F. Belardo, E.M. Li Marzi, S.K. Simi´ c, J. Wang, On the spectral r adius of unicyclic graphs with prescribed degree sequence, Linear Algebra Appl., 432 (2010), 2323–2334

work page 2010
[2]

Bıyıko˘ glu, J

T. Bıyıko˘ glu, J. Leydold, Graphs with given degree sequence and maximal spectral raidus, Electron. J. Combin. , 15 (2008), #R119

work page 2008
[3]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory with Applications , Macmillan Press, New York, 1976

work page 1976
[4]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c,Eigenspaces of Graphs , Cambridge University Press, 1997

work page 1997
[5]

Horn, C.R

R.A. Horn, C.R. Johnson, Matrix Analysis , Reprinted with corrections, Cambridge University Press, 1990

work page 1990
[6]

Huang, B

Y. Huang, B. Liu, Y. Liu, The signless Laplacian spectral raidus of bicyclic graphs with prescribed degree sequences, Discrete Math. , 311 (2011), 504–511

work page 2011
[7]

Jiang, Y

X. Jiang, Y. Liu, B. Liu, A further result on majoriation theorem, Linear Multilinear Algebra, 59 (2011), 957–967

work page 2011
[8]

B. Liu, M. Liu, The majorization theorem of extremal pseudogra phs, Linear Algebra Appl., 459 (2014), 13–22. 31

work page 2014

Show all 20 references

[9]

B. Liu, M. Liu, Z. You, The majorization theorem for signless Lapla cian spectral radii of connected graphs, Graph Combin. , 29 (2013), 281–287

2013
[10]

Liu, The (signless Laplacian) spectral radii of connected gr aphs with prescribed degree sequences, Electron

M. Liu, The (signless Laplacian) spectral radii of connected gr aphs with prescribed degree sequences, Electron. J. Combin. , 19 (2012), #R35

2012
[11]

M. Liu, B. Liu, Some results on the majorization theorem of conn ected graphs, Acta Math. Sin. (Eng. Ser. ), 28 (2012), 371–378

2012
[12]

M. Liu, B. Liu, Extremal Theory of Graph Spectrum, Mathematical Chemistry Mono- graphs, Kragujevac, 2018

2018
[13]

M. Liu, B. Liu, K.C. Das, Recent results on the majorization theo ry of graph spec- trum and topological index theory-a survey, Electron. J. Linear Algebra , 30 (2015), 402–421

2015
[14]

Q. Liu, Y. Hong, X. Gu, H.-J. Lai, Note on edge-disjoint spanning trees andeigen- values, Linear Algebra Appl. , 458 (2014), 128–133

2014
[15]

Y. Liu, B. Liu, The spectral radius of bicyclic graphs with prescr ibed degree se- quences, Linear Algebra Appl. , 433 (2010), 1015–1023

2010
[16]

Luo, S.-G

K. Luo, S.-G. Guo, The majorization theorems of single-cone tr ees and single-cone unicyclic graphs, Bull. Malays. Math. Sci. Soc. , on line
[17]

Marshall, I

A.W. Marshall, I. Olkin, Inequalities: Theory of Majorization and its Applications , Academic Press, New York, 1979

1979
[18]

Zhang, The Laplacian spectral radii of trees with degree sequences, Discrete Math., 308 (2008), 3143–3150

X.-D. Zhang, The Laplacian spectral radii of trees with degree sequences, Discrete Math., 308 (2008), 3143–3150

2008
[19]

Zhang, The signless Laplacian spectral raidus of graphs w ith given dgree se- quences, Discrete Appl

X.-D. Zhang, The signless Laplacian spectral raidus of graphs w ith given dgree se- quences, Discrete Appl. Math. , 157 (2009), 2928–2937. 32

2009
[20]

Zhang, Extremal graph theory for degree sequences, arXiv:1510.01903vl [math.co], 2015

X.-D. Zhang, Extremal graph theory for degree sequences, arXiv:1510.01903vl [math.co], 2015. 33

2015 arXiv

Pith tools

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

[1] [1]

Belardo, E.M

F. Belardo, E.M. Li Marzi, S.K. Simi´ c, J. Wang, On the spectral r adius of unicyclic graphs with prescribed degree sequence, Linear Algebra Appl., 432 (2010), 2323–2334

work page 2010

[2] [2]

Bıyıko˘ glu, J

T. Bıyıko˘ glu, J. Leydold, Graphs with given degree sequence and maximal spectral raidus, Electron. J. Combin. , 15 (2008), #R119

work page 2008

[3] [3]

Bondy, U.S.R

J.A. Bondy, U.S.R. Murty, Graph Theory with Applications , Macmillan Press, New York, 1976

work page 1976

[4] [4]

Cvetkovi´ c, P

D. Cvetkovi´ c, P. Rowlinson, S. Simi´ c,Eigenspaces of Graphs , Cambridge University Press, 1997

work page 1997

[5] [5]

Horn, C.R

R.A. Horn, C.R. Johnson, Matrix Analysis , Reprinted with corrections, Cambridge University Press, 1990

work page 1990

[6] [6]

Huang, B

Y. Huang, B. Liu, Y. Liu, The signless Laplacian spectral raidus of bicyclic graphs with prescribed degree sequences, Discrete Math. , 311 (2011), 504–511

work page 2011

[7] [7]

Jiang, Y

X. Jiang, Y. Liu, B. Liu, A further result on majoriation theorem, Linear Multilinear Algebra, 59 (2011), 957–967

work page 2011

[8] [8]

B. Liu, M. Liu, The majorization theorem of extremal pseudogra phs, Linear Algebra Appl., 459 (2014), 13–22. 31

work page 2014