On the signless Laplacian spectral radius of $K_{s,t}$-minor free graphs

Ming-Zhu Chen; Xiao-Dong Zhang

REVIEW 2 major objections 4 minor 16 references

On the signless Laplacian spectral radius of $K_{s,t}$-minor free graphs

T0 review · 2 major / 4 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 For $K_{2,t}$-minor-free graphs of large order, the signless Laplacian spectral radius obeys a sharp closed-form upper bound, with equality exactly on the join graph $F_{2,t}(n)$; the $K_{3,3}$-minor-free case is also settled for $n\ge…

desk verdict Sharp signless Laplacian bounds for K2,3- and K3,3-minor-free graphs, with the K3,3 case resting on four unproved adapted lemmas that need proof or exact reference. read the letter →

arxiv 1908.04221 v1 pith:AI4IPHAI submitted 2019-08-12 math.CO

Ming-Zhu Chen , Xiao-Dong Zhang This is my paper · ORCID

classification math.CO MSC 05C5005C3505C83

keywords signlessLaplacianspectralradiusminor-freegraphsextremalgraphtheoryK2t-minorfreeK33-minorQ-indexPerron-Frobeniustheoremeigenvalues

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 identifies the exact graphs that maximize the signless Laplacian spectral radius, the largest eigenvalue of $D(G)+A(G)$, among graphs with no $K_{2,t}$ minor and, for large order, no $K_{3,3}$ minor. It proves a closed-form upper bound and shows that equality holds exactly on the join family $F_{s,t}(n)=K_{s-1}\vee(p\cdot K_t\cup K_r)$ under a residue condition; in the $K_{2,3}$ case the maximizer is unique for $n\ge22$, and in the $K_{3,3}$ case for $n\ge1186$. This matters because it turns a forbidden-minor structural condition into a sharp spectral inequality, giving the first signless Laplacian extremal results for these minor classes beyond the previously known $K_{2,2}$ case.

What carries the argument

The load-bearing family is $F_{s,t}(n)=K_{s-1}\vee(p\cdot K_t\cup K_r)$, where $n-s+1=pt+r$ and $0\le r<t$: a clique of $s-1$ universal vertices joined to disjoint copies of $K_t$ and one $K_r$. The proof first shows that a spectral extremal graph must be edge-maximal, then uses Perron–Frobenius and a degree-weighted inequality to force one universal vertex for $K_{2,t}$ or two universal vertices for $K_{3,3}$. Once those universal vertices exist, the remaining graph must consist of disjoint triangles and at most a path of length 1 or 2, and the paper proves by explicit edge switches that any longer path would raise $q(G)$, contradicting maximality. Four adapted degree-sequence lemmas carry the delicate step of capping $q$ at $n+2$ for graphs with near-universal but not universal vertices.

What would settle it

Enumerate all degree sequences satisfying the hypotheses of Lemmas 2.5–2.8 near the thresholds and compute the signless Laplacian spectral radius; a single sequence with $q(G)>n+2$ would break the key bound that forces the $K_{3,3}$ extremal graph to contain two universal vertices. Alternatively, build an edge-maximal $K_{3,3}$-minor-free graph with two universal vertices and one remaining path of length 3; the proof's switching argument predicts it cannot be extremal, so any such graph with $q$ exceeding $q(F_{3,3}(n))$ would refute Theorem 1.4.

Watch

Extended reading notes

Core claim

On its own terms, the discovery is an extremal classification. If $G$ has no $K_{2,t}$ minor and order $n\ge t^2+4t+1$ with $t\ge3$, then $q(G)\le \frac{n+2t-2+\sqrt{(n-2t+2)^2+8t-8}}{2}$, with equality precisely when $n\equiv1\pmod t$ and $G=F_{2,t}(n)$. For $t=3$ this sharpens to the statement that for $n\ge22$, $F_{2,3}(n)$ is the unique maximizer. For $K_{3,3}$-minor-free graphs, the paper shows that for $n\ge1186$ the unique maximizer is $F_{3,3}(n)$, with $q(F_{3,3}(n))$ the largest root of the displayed cubic. The paper also states what it calls Conjecture 4.4: for $2\le s\le t$ and sufficiently large $n$, $F_{s,t}(n)$ should be the unique maximizer among $K_{s,t}$-minor-free graphs.

Load-bearing premise

The $K_{3,3}$ proof depends on four degree-sequence lemmas taken from earlier work in slightly changed forms; the paper says these altered forms are correct but does not prove them, and if any one fails, the conclusion that the extremal graph must have two universal vertices collapses.

Editorial extensions

If this is right

For $K_{2,3}$-minor-free graphs with $n\ge22$, the maximum signless Laplacian spectral radius is exactly $q(F_{2,3}(n))$, the largest root of the cubic in Lemma 2.3(ii), and $F_{2,3}(n)$ is the unique extremal graph.
For $t\ge4$, the upper bound is tight exactly when $n\equiv1\pmod t$; in other residue classes the inequality is strict, so the theorem leaves the exact maximum open for those orders.
For $K_{3,3}$-minor-free graphs of order $n\ge1186$, $F_{3,3}(n)$ is the unique extremal graph, completely settling the $Q$-spectral extremal problem for this minor class at large orders.
The extremal graphs in all settled cases are edge-maximal and contain one or two universal vertices, so any future counterexample would have to avoid that structure.
The paper's Conjecture 4.4 says the same join family $F_{s,t}(n)$ should maximize $q$ among all $K_{s,t}$-minor-free graphs for $2\le s\le t$ and sufficiently large $n$.

Reading between the lines

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

The residue condition $n\equiv1\pmod t$ looks like a technical artifact: for orders in other residue classes the stated bound is not attained, and the natural prediction is that $F_{2,t}(n)$ still maximizes $q$, merely with a value strictly below the bound.
The explicit edge-switch arguments suggest a general smoothing principle for the signless Laplacian: in spectral extremal minor-free graphs, long pendant paths are unstable, so extremal graphs should always be highly clustered unions of cliques around a small universal core.
The four adapted degree-sequence lemmas are the fragile hinge of the $K_{3,3}$ proof; checking them computationally on degree sequences near $n=1186$ would be a cheap way to test whether the structural conclusion is sound.
If the same strategy is pushed to general $K_{s,t}$, the thresholds should grow polynomially in $t$ rather than exponentially, and the current bounds $t^2+4t+1$ and $1186$ are the natural starting points.

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

The paper gives the first sharp signless Laplacian spectral radius bounds for K2,3-minor-free and K3,3-minor-free graphs of large order, with the extremal graphs identified. Theorems 1.2 and 1.3 are convincing and largely self-contained. Theorem 1.4 is plausible but propped up by four lemmas imported from a planar graph paper, stated in modified form, with no proof or exact reference.

What is genuinely new: the equality characterizations for K2,t-minor-free graphs, including the t=3 case with the explicit polynomial for q(F2,3(n)), and the unique extremal graph among K3,3-minor-free graphs. The proof of Theorem 1.2 is a clean structural argument: Lemma 2.1 forces a universal vertex, then G−u is a union of triangles plus at most one short path. The switching claims are terse but check out. Theorem 1.3 is a neat reduction to the existing K2,t-free result, with a short argument that the (t−1)-regular extremal graph must decompose into K_t's.

The soft spot is real and load-bearing for Theorem 1.4. Lemmas 2.5–2.8 are introduced as "a little different from their original forms" in [16], which is about planar graphs with edge bound 3n−6; here the edge bound is 3n−5 and the constants have been adjusted accordingly. These lemmas are used exactly where the proof must rule out Δ′ ≤ n−2, so without them the second universal vertex is not forced. The authors assert the modifications are correct "according to original proofs," but a referee cannot verify that without a theorem-by-theorem reconciliation. This is a genuine gap, not a minor citation issue.

There is also a small slip in Lemma 4.2, Subcase 2.2: if v and v2 are both outside N(v1) and adjacent, they get a third common neighbour, so the bound should be n+3 rather than n+2. It does not change the conclusion—the cap of 65 still holds—but it should be corrected.

Bottom line: the K2,3 and general K2,t results are solid and worth having; the K3,3 result is likely true but not fully verified as written. This deserves a serious referee: send it out with a request to prove or precisely cite the modified lemmas.

Referee Report

2 major / 4 minor

Summary. The paper studies the signless Laplacian spectral radius q(G) of K_{s,t}-minor-free graphs. Its main results are: (i) for K_{2,3}-minor-free graphs of order n≥22, q(G) ≤ q(F_{2,3}(n)) with equality if and only if G=F_{2,3}(n); (ii) for t≥4 and K_{2,t}-minor-free graphs of order n≥t^2+4t+1, q(G) ≤ (n+2t−2+√((n−2t+2)^2+8t−8))/2 with equality if and only if n≡1 (mod t) and G=F_{2,t}(n); and (iii) for K_{3,3}-minor-free graphs of order n≥1186, q(G) ≤ q(F_{3,3}(n)) with equality if and only if G=F_{3,3}(n). The proofs combine spectral perturbation arguments with known edge-density and degree-sequence results. The paper also proposes Conjecture 4.4 for general K_{s,t}-minor-free graphs of large order.

Significance. If the missing justifications are supplied, the results constitute a meaningful contribution to spectral extremal graph theory for minor-closed graph classes. Theorems 1.2 and 1.3 are essentially self-contained modulo cited lemmas and give sharp, explicit upper bounds together with unique extremal graphs. The paper makes good use of Perron-Frobenius theory, Rayleigh quotient inequalities, and known edge-density bounds. The main caveat is that Theorem 1.4 depends on four degree-sequence lemmas (Lemmas 2.5–2.8) that are stated in adapted form without proof or a precise reference; if those lemmas are correct, the K_{3,3} result is plausible and well supported otherwise.

major comments (2)

[Section 2 (Lemmas 2.5–2.8)] The paper states that Lemmas 2.5–2.8 are 'a little different from their original forms [16], but indeed they are correct according to original proofs,' yet it neither proves them nor identifies the exact statements in [16] from which they follow. These lemmas are load-bearing for Theorem 1.4: Lemma 4.2 Case 1 invokes Lemmas 2.5 and 2.6, and Lemma 4.3 Case 1 invokes Lemmas 2.7 and 2.8, to obtain the crucial bound q(G) ≤ n+2. If any of the adapted lemmas fails, the proof cannot force Δ(G)=Δ′(G)=n−1, and the uniqueness of F_{3,3}(n) collapses. The adaptation is nontrivial because [16] concerns planar graphs with e(G) ≤ 3n−6, whereas K_{3,3}-minor-free graphs can have e(G) ≤ 3n−5; the changed constants and ranges are essential to the edge-count inequalities in Lemmas 4.2 and 4.3. The authors must provide full proofs of the adapted lemmas or a detailed derivation from the original results.
[Section 4 (Theorem 1.4 Claim, Cases 1–3; also Theorem 1.2 Claim)] The proofs repeatedly assert 'Clearly G′ is K2,3-minor free' or 'Clearly G′ is K3,3-minor free' after adding edges to path endpoints or performing edge switches (e.g., Theorem 1.2 Cases 1–3, Theorem 1.4 Cases 1–3). These assertions are load-bearing, because the contradiction relies on G′ being minor-free and having a larger signless Laplacian spectral radius. The claims are likely correct, but they require at least a short argument showing that the described operations cannot create the forbidden minor from the path/triangle structure. The authors should supply these justifications rather than leaving them to the reader.

minor comments (4)

[Proof of Theorem 1.4] The text contains a typo: 'Perron–Fronbenius' should be 'Perron–Frobenius'.
[Proofs of Theorems 1.2 and 1.3] There are minor language errors: 'Furtherer' in Theorem 1.2 should be 'Further', and 'combing' in Theorem 1.3 should be 'combining'.
[Lemma 4.1] In the displayed inequality, the parentheses are unbalanced: the term should read '(e(G) − d(u) − e(N(u)))' with a closing parenthesis before the equal sign.
[Lemmas 2.5 and 2.7] The notation 'n/6 + 1 ≤ d_{k+1} ≤ · · · ≤ d_2 ≤ n − 61' is confusing because degree sequences are nonincreasing; rewriting the hypotheses as d_2 ≤ n−61 and d_{k+1} ≥ n/6+1 would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: all load-bearing results are external theorems or direct spectral computations, not self-citations or fitted inputs.

full rationale

The derivation chain is self-contained in the relevant sense. Theorem 1.2 builds on Lemma 2.1, Theorem 1.3 builds on Lemma 2.2, and Theorem 1.4 builds on Lemmas 2.5-2.8 and 4.1-4.3; all of these are either proved in the paper or cited from prior work by non-overlapping authors, so there is no self-citation chain carrying the argument. The extremal candidates F_{s,t}(n) are defined independently and their signless Laplacian spectral radii are computed directly in Lemma 2.3 rather than being fitted from the target bound. No parameter is calibrated to a subset of the data, no quantity that is meant to be predicted is used as an input, and no uniqueness claim is imported from the authors' own prior work as an external fact. The paper's statement that Lemmas 2.5-2.8 are 'a little different from their original forms' but correct is a possible proof-completeness gap, not circularity: the lemmas come from an external source, and the paper does not redefine its conclusion in terms of them. If the adaptations are incorrect, the proof of Theorem 1.4 would fail, but that is a correctness risk rather than a circularity, and the hard rules require an exhibited reduction of the result to its own inputs, which is not present here.

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

No free parameters or invented entities appear; the derivation is combinatorial. The axioms are standard mathematical facts and published theorems from [4,5,6,8,16] that the paper relies on without reproving.

assumptions (7)

standard math Perron-Frobenius theorem for irreducible nonnegative matrices
Used to guarantee a positive eigenvector for q(G) and to compare spectral radii; invoked in Lemma 2.9 and throughout.
domain assumption Lemma 2.2 from [8]: K2,t-free graphs of order n ≥ t^2+4t+1 satisfy the stated q bound, with equality iff G = K1 ∨ H for (t-1)-regular H
Provides the upper bound for Theorem 1.3 and the starting equality structure; the paper does not reprove it.
domain assumption Lemma 2.1 from [8]: K2,3-free graphs of order n ≥ 22 with maximum degree at most n-2 have q < n
Used in Theorem 1.2 to force a universal vertex.
domain assumption Lemma 2.4 from [5]: K1,t-minor free graphs of order n ≥ t+2 have at most n + t(t-3)/2 edges
Used in Theorem 1.3 to rule out non-clique components in the (t-1)-regular part.
domain assumption Lemmas 2.5 through 2.8 from [16] as modified by the authors
Degree-sequence bounds that force q ≤ n+2 under certain degree conditions; the modifications are asserted but not proved.
domain assumption Edge bound e(G) ≤ 3n-5 for K3,3-minor free graphs from [6]
Used in Lemmas 4.1 and 4.2 to bound neighbor degree sums.
domain assumption Edge bound e(N(u)) ≤ 2d(u)-2 for K2,3-minor free induced subgraphs from [4]
Used in Lemma 4.1 to bound the sum of degrees of neighbors of a high-degree vertex.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the signless Laplacian spectral radius of $K_{s,t}$-minor free graphs." pith.science (2026). https://pith.science/paper/AI4IPHAI

@misc{pith2026190804221,
  author       = {Pith},
  title        = {Pith review of: On the signless Laplacian spectral radius of $K_s,t$-minor free graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AI4IPHAI}},
  note         = {Machine review of arXiv:1908.04221}
}

abstract

In this paper, we prove that if $G$ is a $K_{2,t}$-minor free graph of order $n\geq t^2+4t+1$ with $t\geq 3$, the signless Laplacian spectral radius $q(G)\leq \frac{1}{2}(n+2t-2+\sqrt{(n-2t+2)^2+8t-8}\ )$ with equality if and only if $n\equiv 1~(\mathrm{mod}~t)$ and $G=F_{2,t}(n)$, where $F_{s,t}(n):=K_{s-1}\vee (p\cdot K_t\cup K_r)$ for $n-s+1=pt+r$ and $0\leq r<t$. In particular, if $t=3$ and $n\geq 22$, then $F_{2,3}(n)$ is the unique $K_{2,3}$-minor free graph of order $n$ with the maximum signless Laplacian spectral radius. In addition, $F_{3,3}(n)$ is the unique extremal graph with the maximum signless Laplacian spectral radius among all $K_{3,3}$-minor free graphs of order $n\ge 1186$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

[16]

G. Yu, J. Wang, S.-G. Guo, Maxima of the signless Laplacian spect ral radius for planar graphs, Electron. J. Linear Algebra 30 (2015) 795–811. 11

work page 2015
[1]

V. I. Benediktovich, Spectral radius of K2,4-minor free graph, Dokl. Nats. Akad. Nauk Belarusi 59 (2015) 5–12 (in Russian)

work page 2015
[2]

Berman, R

A. Berman, R. J. Plemmons, Nonegative Matrices in the Mathemat ical Sciences, Aca- demic Press, New York (1994)

work page 1994
[3]

J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York , 2007

work page 2007
[4]

Chudnovsky, B

M. Chudnovsky, B. Reed, P. Seymour, The edge-density for K2,t minors, J. Combin. Theory Ser. B 101 (2011) 18–46

work page 2011
[5]

G. Ding, T. Johnson, P. Seymour, Spanning trees with many leave s, J. Graph Theory 37 (2001) 189–197. 10

work page 2001
[6]

Fang, Bounds of eigenvalues of K3,3-minor free graphs, J

K.-F. Fang, Bounds of eigenvalues of K3,3-minor free graphs, J. Inequal. Appl. 2009 (2009) 1–6

work page 2009
[7]

M. A. A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013) 905–916

work page 2013

Show all 16 references

[8]

M. A. A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: graphs with no Ks,t, Linear Algebra Appl. 496 (2016) 381–391

2016
[9]

Hong, Tree-width, clique-minors, and eigenvalues, Discrete M ath

Y. Hong, Tree-width, clique-minors, and eigenvalues, Discrete M ath. 274 (2004) 281– 287

2004
[10]

Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl

R. Merris, A note on Laplacian graph eigenvalues, Linear Algebra Appl. 285 (1998) 33–35

1998
[11]

Nikiforov, The spectral radius of graphs with no K2,t-minor, Linear Algebra Appl

V. Nikiforov, The spectral radius of graphs with no K2,t-minor, Linear Algebra Appl. 531 (2017) 510–515

2017
[12]

J. Shu, Y. Hong, The spectral radius of K4-minor free graph, Acta Math. Appl. Sinica 5 (2001) 167–175

2001
[13]

Tait, The Colin de Verdi` ere parameter, excluded minors, an d the spectral radius, J

M. Tait, The Colin de Verdi` ere parameter, excluded minors, an d the spectral radius, J. Combin. Theory Ser. A 166 (2019), 42-58

2019
[14]

Wagner, ¨Uber eine Eigenschaft der ebenen Komplexe, Math

K. Wagner, ¨Uber eine Eigenschaft der ebenen Komplexe, Math. Ann. 114 (1937 ) 570– 590

1937
[15]

G. Yu, J. Shu, Y. Hong, Bounds of spectral radii of K2,3-minor free graphs, Electron. J. Linear Algebra 23 (2012) 171–179

2012

Pith tools

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

[1] [16]

G. Yu, J. Wang, S.-G. Guo, Maxima of the signless Laplacian spect ral radius for planar graphs, Electron. J. Linear Algebra 30 (2015) 795–811. 11

work page 2015

[2] [1]

V. I. Benediktovich, Spectral radius of K2,4-minor free graph, Dokl. Nats. Akad. Nauk Belarusi 59 (2015) 5–12 (in Russian)

work page 2015

[3] [2]

Berman, R

A. Berman, R. J. Plemmons, Nonegative Matrices in the Mathemat ical Sciences, Aca- demic Press, New York (1994)

work page 1994

[4] [3]

J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, New York , 2007

work page 2007

[5] [4]

Chudnovsky, B

M. Chudnovsky, B. Reed, P. Seymour, The edge-density for K2,t minors, J. Combin. Theory Ser. B 101 (2011) 18–46

work page 2011

[6] [5]

G. Ding, T. Johnson, P. Seymour, Spanning trees with many leave s, J. Graph Theory 37 (2001) 189–197. 10

work page 2001

[7] [6]

Fang, Bounds of eigenvalues of K3,3-minor free graphs, J

K.-F. Fang, Bounds of eigenvalues of K3,3-minor free graphs, J. Inequal. Appl. 2009 (2009) 1–6

work page 2009

[8] [7]

M. A. A. de Freitas, V. Nikiforov, L. Patuzzi, Maxima of the Q-index: forbidden 4-cycle and 5-cycle, Electron. J. Linear Algebra 26 (2013) 905–916

work page 2013