pith. sign in

arxiv: 2605.23737 · v1 · pith:63EOZ3EQnew · submitted 2026-05-22 · 🧮 math.CO

Spectral radius and edge-disjoint connected factors of graphs

Xinying Tang , Wenqian Zhang This is my paper

Pith reviewed 2026-05-25 03:51 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral radiusedge-disjoint factors2-connected factorsspanning treesminimum degreegraph decompositionadjacency matrix
0
0 comments X

The pith

A sharp bound on the largest adjacency eigenvalue guarantees k edge-disjoint 2-connected spanning subgraphs plus floor((δ-4k)/2) edge-disjoint spanning trees in graphs of order n with minimum degree δ ≥ 6 and n ≥ 3δ, for 1 ≤ k ≤ floor(δ/4).

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

The paper gives a spectral radius threshold that forces a graph meeting the minimum-degree and order conditions to decompose into the stated collection of edge-disjoint connected factors. The threshold is shown to be best possible by exhibiting an extremal graph that attains equality yet just meets the factor counts. A reader cares because the spectral radius is a single, easily computed number that can certify the existence of these multiple disjoint connected spanning subgraphs without constructing them explicitly. The result therefore supplies a practical sufficient condition for the desired decomposition under the stated degree regime.

Core claim

Let G be a graph of order n with minimum degree δ ≥ 6 and n ≥ 3δ. If the spectral radius of G is at least as large as that of a certain extremal graph on the same number of vertices, then G contains k edge-disjoint 2-connected factors together with floor((δ-4k)/2) edge-disjoint spanning trees whenever 1 ≤ k ≤ floor(δ/4).

What carries the argument

The spectral radius (largest eigenvalue of the adjacency matrix) compared against the radius of a specific extremal graph that serves as the sharpness example.

If this is right

  • The extremal graphs achieving the spectral radius bound realize exactly the guaranteed factor counts and no more.
  • For each admissible k the same spectral condition simultaneously certifies both the 2-connected factors and the additional spanning trees.
  • The result recovers earlier degree conditions on the existence of such factors when the spectral radius is large enough.
  • The bound applies uniformly across the entire range 1 ≤ k ≤ floor(δ/4).

Where Pith is reading between the lines

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

  • The same spectral condition might be checked algorithmically on moderately sized graphs to certify the existence of multiple edge-disjoint 2-connected spanning subgraphs.
  • If the spectral radius is slightly below the threshold, the graph may still possess the factors, but the proof technique would need a different argument.
  • The decomposition into 2-connected factors plus trees could be used to design networks that remain connected after removal of up to k-1 edge sets while retaining tree-like redundancy in the remainder.

Load-bearing premise

The minimum-degree threshold δ ≥ 6 together with the order condition n ≥ 3δ must hold for the spectral radius bound to be both sufficient and sharp.

What would settle it

Exhibit a graph G with δ ≥ 6, n ≥ 3δ, whose spectral radius meets or exceeds the stated threshold, yet which fails to contain the claimed number of edge-disjoint 2-connected factors or spanning trees.

read the original abstract

For a graph $G$, the spectral radius of $G$ is the largest eigenvalue of its adjacency matrix. A connected factor of $G$ is a connected spanning subgraph of $G$. For example, a spanning tree of $G$ is a 1-connected factor of $G$. Let $G$ be a graph of order $n$ with minimum degree $\delta\geq6$, where $n\geq3\delta$. In this paper, we give a sharp spectral radius condition for $G$ to contain $k$ edge-disjoint 2-connected factors and $\left\lfloor\frac{\delta-4k}{2}\right\rfloor$ edge-disjoint spanning trees, where $1\leq k\leq\left\lfloor\frac{\delta}{4}\right\rfloor$ is an integer.

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 / 1 minor

Summary. The paper claims that for a graph G of order n with minimum degree δ ≥ 6 and n ≥ 3δ, there exists a sharp spectral radius condition guaranteeing that G contains k edge-disjoint 2-connected factors together with floor((δ-4k)/2) edge-disjoint spanning trees, for each integer k satisfying 1 ≤ k ≤ floor(δ/4).

Significance. If the claimed sharp threshold holds with a correct proof, the result would extend spectral Turán-type theorems to the setting of multiple edge-disjoint connected factors, giving a combined degree-spectral guarantee that is potentially useful for decomposition problems in graph theory.

major comments (2)
  1. [Abstract] Abstract: the central claim asserts the existence of a 'sharp spectral radius condition' but neither states the explicit bound on the spectral radius nor supplies any proof steps or reference to the relevant theorem/equation; without this the sufficiency and sharpness assertions cannot be examined.
  2. The minimum-degree and order hypotheses (δ ≥ 6, n ≥ 3δ) are presented as the regime in which the bound is both sufficient and sharp, yet no supporting derivation or extremal example is visible in the provided text, leaving the load-bearing claim unverified.
minor comments (1)
  1. [Abstract] The floor expression floor((δ-4k)/2) is introduced without an immediate explanation of why the coefficient 4 appears; a short remark on the origin of the coefficient would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed comments. We address each major comment below and will revise the manuscript to improve clarity and verifiability of the claims.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim asserts the existence of a 'sharp spectral radius condition' but neither states the explicit bound on the spectral radius nor supplies any proof steps or reference to the relevant theorem/equation; without this the sufficiency and sharpness assertions cannot be examined.

    Authors: We agree that the abstract should explicitly state the spectral radius bound to make the central claim verifiable at a glance. The bound appears in Theorem 1.1; we will revise the abstract to include the precise threshold (along with a reference to the theorem) while keeping the abstract concise. Abstracts do not typically contain proof steps, but the reference will direct readers to the relevant section. revision: yes

  2. Referee: The minimum-degree and order hypotheses (δ ≥ 6, n ≥ 3δ) are presented as the regime in which the bound is both sufficient and sharp, yet no supporting derivation or extremal example is visible in the provided text, leaving the load-bearing claim unverified.

    Authors: The derivation of the conditions δ ≥ 6 and n ≥ 3δ is explained in the introduction (paragraph following the statement of the main result) and justified via the edge-count requirements in the proof of Theorem 1.1. The extremal examples establishing sharpness are constructed in Section 3. We will add explicit cross-references from the abstract and introduction to these sections and, if the referee finds them insufficiently prominent, expand the discussion of the extremal graphs. revision: partial

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states a spectral radius threshold guaranteeing the existence of k edge-disjoint 2-connected factors and additional spanning trees under explicit minimum-degree and order conditions (δ ≥ 6, n ≥ 3δ). No self-definitional steps, fitted inputs renamed as predictions, or load-bearing self-citations appear in the abstract or claim formulation. The result is presented as a sufficient condition in a stated regime, with sharpness asserted externally rather than by construction from the inputs themselves. The derivation chain is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definitions and basic properties of the adjacency matrix eigenvalues and of connected factors in undirected graphs; no free parameters, ad-hoc axioms, or invented entities are stated in the abstract.

axioms (2)
  • standard math The spectral radius is the largest eigenvalue of the adjacency matrix of an undirected simple graph.
    Invoked by the definition of the spectral radius condition.
  • domain assumption A connected factor is a connected spanning subgraph; a 2-connected factor remains connected after deletion of any single vertex.
    Used to state the combinatorial conclusion.

pith-pipeline@v0.9.0 · 5654 in / 1359 out tokens · 40037 ms · 2026-05-25T03:51:37.475593+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages · 1 internal anchor

  1. [1]

    Asimov and B

    L. Asimov and B. Roth, The rigidity of graphs, Trans. Am. Math. Soc. 245 (1978) 279-289

    work page 1978

  2. [2]

    Cvetkovi´ c, P

    D. Cvetkovi´ c, P. Rowlinson and S. Simi´ c, An Introduction to the Theory of Graph Spectra, Cambridge University Press, Cambridge, 2010

    work page 2010

  3. [3]

    Cioab˘ a, S

    S. Cioab˘ a, S. Dewar and X. Gu. Spectral conditions for graph rigidity in the Euclidean plane, Discrete Math. 344 (2021) 112527

    work page 2021

  4. [4]

    Cioab˘ a and W

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

    work page 2012

  5. [5]

    Cioab˘ a, A

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

    work page 2022

  6. [6]

    Cheriyan, O

    J. Cheriyan, O. Durand de Gevigney and Z. Szigeti, Packing of rigid spanning sub- graphs and spanning trees, J. Comb. Theory, Ser. B 105 (2014) 17-25

    work page 2014

  7. [7]

    Cucuringu, A

    M. Cucuringu, A. Singer and D. Cowburn, Eigenvector synchronization, graph rigidity and the molecule problem, Inf. Inference 1 (2012) 21-67

    work page 2012

  8. [8]

    Cai and B

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

    work page 2026

  9. [9]

    C. Duan, L. Wang and X. Liu, Edge Connectivity, Packing Spanning Trees, and Eigenvalues of Graphs, Linear Multilinear A. 68 (2020) 1077-1095

    work page 2020

  10. [10]

    Edmonds, Matroid partition, in: Mathematics of the Decision Sciences Part 1, Lectures in Applied Mathematics, vol

    J. Edmonds, Matroid partition, in: Mathematics of the Decision Sciences Part 1, Lectures in Applied Mathematics, vol. 11,AMS, Providence, RI, 1968, pp. 335-345. 17

    work page 1968

  11. [11]

    D. Fan, X. Gu and H. Lin, Spectral Radius and Edge-Disjoint Spanning Trees, J. Graph Theor. 104 (2023) 697-711

    work page 2023

  12. [12]

    D. Fan, X. Huang and H. Lin, Spectral radius conditions for the rigidity of graphs, Electron. J. Comb. 30(2) (2023) #P2.14

    work page 2023

  13. [13]

    X. Gu, H. Lai, P. Li and S. Yao, Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs, Journal of Graph Theory 81 (2016) 16-29

    work page 2016

  14. [14]

    G´ asp´ ar and P

    M. G´ asp´ ar and P. Csermely, Rigidity and flexibility of biological networks, Brief. Funct. Genomics 11 (2012) 443-456

    work page 2012

  15. [15]

    Graver, B

    J. Graver, B. Servatius and H. Servatius, Combinatorial Rigidity, Graduate Studies in Mathematics, vol. 2, American Mathematical Society, 1993

    work page 1993

  16. [16]

    Gu, Packing spanning trees and spanning 2-connectedk-edge-connected essentially (2k−1)-edge-connected subgraphs, J

    X. Gu, Packing spanning trees and spanning 2-connectedk-edge-connected essentially (2k−1)-edge-connected subgraphs, J. Comb. Optim. 33 (2017) 924-933

    work page 2017

  17. [17]

    Gu, Spanning rigid subgraph packing and sparse subgraph covering, SIAM J

    X. Gu, Spanning rigid subgraph packing and sparse subgraph covering, SIAM J. Discrete Math. 32 (2018) 1305-1313

    work page 2018

  18. [18]

    Gao and L

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

    work page 2026

  19. [19]

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

    Y. Gao and L. Wang, Spectral radius and edge-disjoint spanning trees of (k+ 1)- edge-connected graphs, arXiv:2604.21470v1

    work page internal anchor Pith review Pith/arXiv arXiv

  20. [20]

    Y. Hong, J. Shu and K. Fang, A sharp upper bound of the spectral radius of graphs, J. Comb. Theory, Ser. B 81 (2001) 177-183

    work page 2001

  21. [21]

    Y. Hu, L. Wang and C. Duan, Spectral Conditions for Edge Connectivity and Span- ning Tree Packing Number in (Multi-) Graphs, Linear Algebra Appl. 664 (2023) 324-348

    work page 2023

  22. [22]

    Kirchhoff, ¨Uber die Aufl¨ oung der Gleichungen, auf welche man bei der unter- suchung der linearen verteilung galvanischer Str¨ ome gef¨ uhrt wird, Ann

    G. Kirchhoff, ¨Uber die Aufl¨ oung der Gleichungen, auf welche man bei der unter- suchung der linearen verteilung galvanischer Str¨ ome gef¨ uhrt wird, Ann. Phys. Chem. 72 (1847) 497-508

    work page

  23. [23]

    Li and L

    G. Li and L. Shi, Edge-Disjoint Spanning Trees and Eigenvalues of Graphs, Linear Algebra Appl. 439 (2013) 2784-2789

    work page 2013

  24. [24]

    Q. Liu, Y. Hong and H. Lai, Edge-Disjoint Spanning Trees and Eigenvalues, Linear Algebra Appl. 444 (2014) 146-151. 18

    work page 2014

  25. [25]

    Q. Liu, Y. Hong, X. Gu and H. Lai, Note on Edge-Disjoint Spanning Trees and Eigenvalues, Linear Algebra Appl. 458 (2014) 128-133

    work page 2014

  26. [26]

    Jackson and T

    B. Jackson and T. Jord´ an, Connected rigidity matroids and unique realizations of graphs, J. Comb. Theory, Ser. B 94 (2005) 1-29

    work page 2005

  27. [27]

    Jackson, T

    B. Jackson, T. Jord´ an, A sufficient connectivity condition for generic rigidity in the plane, Discrete Appl. Math. 157 (2009) 1965-1968

    work page 2009

  28. [28]

    Jord´ an, On the existence ofkedge-disjoint 2-connected spanning subgraphs, J

    T. Jord´ an, On the existence ofkedge-disjoint 2-connected spanning subgraphs, J. Comb. Theory, Ser. B 95 (2005) 257-262

    work page 2005

  29. [29]

    Jord´ an, Combinatorial Rigidity: Graphs and Matroids in the Theory of Rigid Frameworks, Discrete Geometric Analysis, MSJ Mem., vol

    T. Jord´ an, Combinatorial Rigidity: Graphs and Matroids in the Theory of Rigid Frameworks, Discrete Geometric Analysis, MSJ Mem., vol. 34, Math. Soc. Japan, Tokyo, 2016, pp. 33-112

    work page 2016

  30. [30]

    Laman, On graphs and rigidity of plane skeletal structures, J

    G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math. 4 (1970) 331-340

    work page 1970

  31. [31]

    Lov´ asz and Y

    L. Lov´ asz and Y. Yemini, On generic rigidity in the plane, SIAM J. Algebraic Discrete Methods 3 (1982) 91-98

    work page 1982

  32. [32]

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

    work page 2019

  33. [33]

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

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

    work page 2002

  34. [34]

    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

  35. [35]

    Oxley, Matroid Theory, Oxford Science Publications, The Clarendon Press, Ox- ford University Press, New York, 1992

    J.G. Oxley, Matroid Theory, Oxford Science Publications, The Clarendon Press, Ox- ford University Press, New York, 1992. xii+532pp

    work page 1992

  36. [36]

    Schrijver, Combinatorial Optimization, Springer, Berlin, 2003

    A. Schrijver, Combinatorial Optimization, Springer, Berlin, 2003

    work page 2003

  37. [37]

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

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

    work page 1961

  38. [38]

    Zelazo, A

    D. Zelazo, A. Franchi, H.H. B¨ ulthoff and P.R. Giordano, Decentralized rigidity main- tenance control with range measurements for multi-robot systems, Int. J. Robot. Res. 34 (2015) 105-128. 19

    work page 2015

  39. [39]

    Zhang and D

    Y. Zhang and D. Fan, Spectral Radius and Edge-Disjoint Spanning Trees of Graphs With Prescribed Edge Connectivity, J. Graph Theor. 112 (2026) 128-144. 20

    work page 2026