pith. sign in

arxiv: 2604.21470 · v2 · submitted 2026-04-23 · 🧮 math.CO

Spectral radius conditions for edge-disjoint spanning trees in (k+c)-edge-connected graphs

Yongbin Gao , Ligong Wang This is my paper

Pith reviewed 2026-05-14 22:06 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C5005C70
keywords spectral radiusedge-disjoint spanning treesspanning tree packing numberedge-connectivityextremal graphsclique constructions
0
0 comments X

The pith

A (k+c)-edge-connected graph contains k edge-disjoint spanning trees once its spectral radius exceeds the value achieved by specific large-clique-plus-small-part constructions.

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

The paper solves an open problem on spectral conditions for the spanning tree packing number by proving tight upper bounds on the spectral radius of (k+c)-edge-connected graphs that fail to have k edge-disjoint spanning trees. These bounds are realized exactly by families of graphs built from a large clique attached to a small vertex set whose internal edges and cross edges are restricted. The same approach yields a tight bound for the (2k-1)-edge-connected case, and for connectivity k+1 the extremal graph is shown to be unique. A reader cares because the spectral radius can be computed from the adjacency matrix alone, offering a practical test that avoids directly searching for the trees or verifying connectivity degrees.

Core claim

For every k ≥ 3 and 1 ≤ c ≤ k-2, if G is (k+c)-edge-connected and its spectral radius is strictly larger than the spectral radius of the maximum member of the described extremal family, then the spanning tree packing number τ(G) is at least k. An analogous tight spectral radius condition holds for (2k-1)-edge-connected graphs. All extremal graphs belong to explicit families whose members consist of a large clique together with a small remaining part that has limited edges inside it and between the parts; the graphs of maximum spectral radius inside each family serve as the extremal examples.

What carries the argument

The extremal graph families formed by a large clique plus a small vertex set with restricted internal and crossing edges; the spectral radius of the largest such graph supplies the threshold that forces τ(G) ≥ k.

If this is right

  • Any (k+c)-edge-connected graph exceeding the spectral threshold must satisfy τ(G) ≥ k.
  • The same spectral test applies directly to the (2k-1)-edge-connected case.
  • For connectivity exactly k+1 the unique graph attaining the maximum spectral radius without the packing property is identified.
  • The constructions show that the bounds cannot be improved by any smaller constant or function of n.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same clique-plus-small-part structure may serve as the extremal examples for other packing problems such as arboricity or disjoint paths.
  • Spectral methods could replace direct search algorithms when checking the existence of k spanning trees in moderately dense graphs.
  • The uniqueness result for c=1 suggests that the threshold becomes rigid at the lowest connectivity levels above k.

Load-bearing premise

The only (k+c)-edge-connected graphs without k edge-disjoint spanning trees are those whose spectral radii are at most the radii of the maximum members of the described clique-plus-small-part families.

What would settle it

A single (k+c)-edge-connected graph whose spectral radius is larger than every member of the extremal family yet whose spanning tree packing number is still less than k would disprove the claimed threshold.

Figures

Figures reproduced from arXiv: 2604.21470 by Ligong Wang, Yongbin Gao.

Figure 1
Figure 1. Figure 1: The graph F1 v4 v3 v1 v2 Kn−4 u1 uk−2uk−1 [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 3
Figure 3. Figure 3: The graphs Fn,k and F ′ n,k with vertex labels Lemma 3.1. For n ≥ 3k + 2 and k ≥ 3, we have ρ(Fn,k) > ρ(F ′ n,k). Proof. Let x be the Perron vector of A(F ′ n,k), and let xw denote the entry of x corresponding to a vertex w ∈ V (F ′ n,k). Since Fn,k = F ′ n,k − v1v2 + v2uk−1, we may apply Lemma 2.3 with u = uk−1, v = v1, and {v2} ⊆ NF ′ n,k (v1) \ NF ′ n,k (uk−1). Thus, it suffices to show that xuk−1 ≥ xv1… view at source ↗
read the original abstract

Let $\tau(G)$ denote the spanning tree packing number of a graph $G$. Recently, Zhang and Fan [J. Graph Theory 112 (2) (2026) 128--144] posed the problem of finding a tight spectral radius condition for an $m$-edge-connected graph $G$ to guarantee $\tau(G)\ge k$ for $k+1\le m\le 2k-1$. They solved the cases $m=k$ and $k=2, m=3$. In this paper, we study this problem for all $m=k+c$, where $1\le c\le k-1$. For $1\le c\le k-2$, we obtain a tight spectral radius condition for a $(k+c)$-edge-connected graph to contain $k$ edge-disjoint spanning trees. We also obtain a tight spectral radius condition for $(2k-1)$-edge-connected graphs. In both cases, we give graph families containing all extremal graphs, and the graphs with maximum spectral radius in these families serve as the corresponding extremal graphs. Each graph in these families consists of a large clique and a small remaining part, with certain restrictions on the edges inside the small part and between the two parts. Moreover, for the case $m=k+1$, we further determine the unique extremal graph.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript establishes tight spectral radius conditions for a (k+c)-edge-connected graph G to satisfy τ(G) ≥ k when 1 ≤ c ≤ k-2, and a separate tight condition for (2k-1)-edge-connected graphs. It identifies explicit families of extremal graphs (each consisting of a large clique plus a small remaining part with restricted edges inside the small part and between the parts) that contain all maximizers of the spectral radius among graphs with τ(G) < k, and for the case m = k+1 it determines the unique extremal graph.

Significance. If the proofs are correct, the work completes the spectral-radius version of the spanning-tree-packing problem for the full range of connectivities k+1 ≤ m ≤ 2k-1, extending the cases already settled by Zhang and Fan. The explicit description of the extremal families and the determination of a unique maximizer for m = k+1 are notable strengths, provided the families are shown to be exhaustive.

major comments (2)
  1. [Section describing the extremal families and the proof of maximality] The central claim that the stated families contain every (k+c)-edge-connected graph with τ(G) < k that attains the maximum possible spectral radius is load-bearing for tightness. The argument ruling out higher-λ₁ graphs with different Nash-Williams violating partitions (outside the large-clique-plus-restricted-small-part construction) must be verified in full; if any such partition yields a strictly larger spectral radius while preserving (k+c)-connectivity, the proposed threshold is not tight.
  2. [Proof of the main spectral-radius theorem for 1 ≤ c ≤ k-2] For the case 1 ≤ c ≤ k-2 the manuscript asserts that the bound is attained inside the families and that no larger spectral radius is possible. The reduction from the general (k+c)-connectivity hypothesis to the specific partition structure used in the extremal examples needs an explicit step showing that any other partition type cannot exceed the claimed radius while keeping τ(G) < k.
minor comments (2)
  1. [Abstract] The abstract states the result for all m = k+c with 1 ≤ c ≤ k-1, yet the body separates the range 1 ≤ c ≤ k-2 from the case m = 2k-1; a single sentence clarifying that c = k-1 is handled by the (2k-1) result would remove ambiguity.
  2. [Notation and family definitions] Notation for the extremal families (e.g., the precise restrictions on edges inside the small part) should be introduced once and used consistently; currently the description appears only in the abstract and the final section.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and for highlighting the importance of verifying the exhaustiveness of the extremal families. We address each major comment below. The proofs in the manuscript already establish the required bounds and maximality, but we agree that an additional clarifying paragraph would improve readability without altering the results.

read point-by-point responses

  1. Referee: [Section describing the extremal families and the proof of maximality] The central claim that the stated families contain every (k+c)-edge-connected graph with τ(G) < k that attains the maximum possible spectral radius is load-bearing for tightness. The argument ruling out higher-λ₁ graphs with different Nash-Williams violating partitions (outside the large-clique-plus-restricted-small-part construction) must be verified in full; if any such partition yields a strictly larger spectral radius while preserving (k+c)-connectivity, the proposed threshold is not tight.

    Authors: Section 4 contains the full argument: any (k+c)-edge-connected graph with τ(G) < k admits a Nash-Williams partition violating the tree-packing condition. We then classify all possible such partitions compatible with the edge-connectivity and show, via direct comparison of the Rayleigh quotient and the Perron vector, that any partition structure other than the large-clique-plus-restricted-small-part form yields a strictly smaller spectral radius than the extremal graphs in the families. The proof is self-contained and rules out higher-λ₁ examples while preserving connectivity; we will add a short summary lemma at the beginning of Section 4 to make the case distinction more explicit. revision: partial

  2. Referee: [Proof of the main spectral-radius theorem for 1 ≤ c ≤ k-2] For the case 1 ≤ c ≤ k-2 the manuscript asserts that the bound is attained inside the families and that no larger spectral radius is possible. The reduction from the general (k+c)-connectivity hypothesis to the specific partition structure used in the extremal examples needs an explicit step showing that any other partition type cannot exceed the claimed radius while keeping τ(G) < k.

    Authors: The reduction appears in the proof of Theorem 1.2 (pages 8–10). After invoking the (k+c)-edge-connectivity to limit the size of the violating sets in the Nash-Williams partition, we apply the spectral-radius upper bound derived from the extremal construction. To make the step fully explicit, we will insert a new paragraph immediately after the connectivity hypothesis is used, stating that any partition whose block sizes deviate from the extremal pattern forces the quadratic form associated with the adjacency matrix to be at most the value attained by the extremal graphs, thereby completing the comparison. revision: yes

Circularity Check

0 steps flagged

No circularity detected; derivation uses independent theorems

full rationale

The paper extends Zhang and Fan's spectral radius problem for tree packing using the Nash-Williams theorem and standard Perron-Frobenius or eigenvalue bounds on edge-connectivity. Extremal families (large clique plus restricted small part) are characterized directly from the (k+c)-connectivity and τ(G)<k conditions rather than being presupposed or fitted. No self-definitional reductions, predictions that reduce to input parameters by construction, or load-bearing self-citations appear; the cited prior work is external and the central claims rest on combinatorial arguments that remain falsifiable outside the fitted spectral thresholds.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Results rest on standard definitions of edge-connectivity, spanning-tree packing number, and spectral radius from prior graph theory literature; no new free parameters, ad-hoc axioms, or invented entities are indicated in the abstract.

pith-pipeline@v0.9.0 · 5540 in / 1071 out tokens · 37241 ms · 2026-05-14T22:06:17.053505+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

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

  1. Spectral radius and edge-disjoint connected factors of graphs

    math.CO 2026-05 unverdicted novelty 4.0

    States a sharp spectral radius threshold for the existence of k edge-disjoint 2-connected factors and floor((δ-4k)/2) edge-disjoint spanning trees in graphs with δ ≥ 6 and n ≥ 3δ.

Reference graph

Works this paper leans on

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

  1. [1]

    J. Cai, B. Zhou, Eigenvalue conditions implying edge-disjoint spanning trees and a forest with constraints, Discrete Math. 349 (2) (2026) 114710

    work page 2026

  2. [2]

    Cioabˇ a, A

    S.M. Cioabˇ a, A. Ostuni, D. Park, S. Potluri, T. Wakhare, W. Wong, Extremal graphs for a spectral inequality on edge-disjoint spanning trees, Electron. J. Combin. 29 (2) (2022) 2.56. 16

    work page 2022

  3. [3]

    Cioabˇ a, W

    S.M. Cioabˇ a, W. Wong, Edge-disjoint spanning trees and eigenvalues of regular graphs, Linear Algebra Appl. 437 (2) (2012) 630–647

    work page 2012

  4. [4]

    Duan, L.G

    C.X. Duan, L.G. Wang, X.X. Liu, Edge connectivity, packing spanning trees, and eigen- values of graphs, Linear Multilinear Algebra 68 (6) (2020) 1077–1095

    work page 2020

  5. [5]

    Fan, X.F

    D.D. Fan, X.F. Gu, H.Q. Lin, Spectral radius and edge-disjoint spanning trees, J. Graph Theory 104 (4) (2023) 697–711

    work page 2023

  6. [6]

    Fan, R.M

    D.D. Fan, R.M. He, Y.H. Zhao, Distance spectral radius and edge-disjoint spanning trees, Discrete Appl. Math. 376 (2025) 31–40

    work page 2025

  7. [7]

    Gao, L.G

    Y.B. Gao, L.G. Wang, Laplacian eigenvalue conditions for edge-disjoint spanning trees and a forest with constraints, Discrete Math. 349 (9) (2026) 115186

    work page 2026

  8. [8]

    X.F. Gu, H.J. Lai, P. Li, S.M. Yao, Edge-disjoint spanning trees, edge connectivity, and eigenvalues in graphs, J. Graph Theory 81 (1) (2016) 16–29

    work page 2016

  9. [9]

    X.F. Gu, R.R. Liu, G.X. Yu, Spanning tree packing and 2-essential edge-connectivity, Discrete Math. 346 (1) (2023) 113132

    work page 2023

  10. [10]

    Hong, J.L

    Y. Hong, J.L. Shu, K.F. Fang, A sharp upper bound of the spectral radius of graphs, J. Combin. Theory Ser. B 81 (2) (2001) 177–183

    work page 2001

  11. [11]

    Y. Hu, L.G. Wang, C.X. Duan, Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs, Linear Algebra Appl. 664 (2023) 324–348

    work page 2023

  12. [12]

    Lai, J.A

    H.J. Lai, J.A. Li, Packing spanning trees in highly essentially connected graphs, Discrete Math. 342 (1) (2019) 1–9

    work page 2019

  13. [13]

    Liu, Y.M

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

    work page 2014

  14. [14]

    Liu, Y.M

    Q.H. Liu, Y.M. Hong, H.J. Lai, Edge-disjoint spanning trees and eigenvalues, Linear Algebra Appl. 444 (2014) 146–151

    work page 2014

  15. [15]

    Liu, H.J

    R.F. Liu, H.J. Lai, Y.Z. Tian, Spanning tree packing number and eigenvalues of graphs with given girth, Linear Algebra Appl. 578 (2019) 411–424

    work page 2019

  16. [16]

    Nash-Williams, Edge-disjoint spanning trees of finite graphs, J

    C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. London Math. Soc. 36 (1961) 445–450

    work page 1961

  17. [17]

    Niculescu, L.-E

    C.P. Niculescu, L.-E. Persson, Convex Functions and Their Applications—A Contempo- rary Approach, Third edition, Springer, Cham, 2025

    work page 2025

  18. [18]

    Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin

    V. Nikiforov, Some inequalities for the largest eigenvalue of a graph, Combin. Probab. Comput. 11 (2) (2002) 179–189

    work page 2002

  19. [19]

    Tutte, On the problem of decomposing a graph intonconnected factors, J

    W.T. Tutte, On the problem of decomposing a graph intonconnected factors, J. London Math. Soc. 36 (1961) 221–230

    work page 1961

  20. [20]

    Wei, Z.F

    J. Wei, Z.F. You, S.L. Song, and H.J. Lai, Spectral and extremal conditions for supereu- lerian graphs, Linear Multilinear Algebra 70 (20) (2022) 5995–6017. 17

    work page 2022

  21. [21]

    B.F. Wu, E.L. Xiao, Y. Hong, The spectral radius of trees onkpendant vertices, Linear Algebra Appl. 395 (2005) 343–349

    work page 2005

  22. [22]

    Zhang, D.D

    Y.K. Zhang, D.D. Fan, Spectral radius and edge-disjoint spanning trees of graphs with prescribed edge connectivity, J. Graph Theory 112 (2) (2026) 128–144. 18

    work page 2026