pith. sign in

arxiv: 2604.27908 · v1 · submitted 2026-04-30 · 🧮 math.CO

Sufficient conditions for spanning k-trees in tough graphs

Caili Jia , Yong Lu This is my paper

Pith reviewed 2026-05-07 06:39 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C0505C50
keywords spanning k-treetoughnessspectral radiussignless Laplacian spectral radiusdegree-bounded treesextremal graph theorysufficient conditions
0
0 comments X

The pith

A connected graph with toughness at least t/(t(k-2)+1) contains a spanning k-tree if its order meets a lower bound or its spectral radius (or signless Laplacian spectral radius) is large enough.

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

The paper refines sufficient conditions for spanning k-trees in graphs whose toughness falls strictly between the classical thresholds of 1/(k-1) and 1/(k-2). It introduces the parameterized toughness lower bound t/(t(k-2)+1) for any positive integer t and proves that any connected graph meeting this bound has a spanning k-tree (a spanning tree with maximum degree at most k) whenever the number of vertices is sufficiently large or the spectral radius is sufficiently large. The same conclusion holds when the signless Laplacian spectral radius replaces the ordinary spectral radius. Specializing to t=1 recovers the earlier spectral results for exactly 1/(k-1)-tough graphs.

Core claim

For integers k ≥ 3 and t ≥ 1, if G is connected and satisfies 1/(k-2) > τ(G) ≥ t/(t(k-2)+1), then G contains a spanning k-tree whenever |V(G)| is at least a stated function of k and t, or the spectral radius ρ(G) meets a corresponding lower bound depending on k and t, or the signless Laplacian spectral radius q(G) meets its own lower bound.

What carries the argument

The parameterized toughness threshold t/(t(k-2)+1), which sits between 1/(k-1) and 1/(k-2), combined with either an order lower bound or an extremal spectral-radius condition to force the existence of a spanning subgraph that is a tree of maximum degree k.

If this is right

  • When t equals 1 the toughness bound reduces to 1/(k-1) and the spectral conditions recover the earlier results of Liu, Fan and Shu.
  • The order-based condition supplies a purely combinatorial sufficient criterion that does not rely on eigenvalues.
  • Analogous statements hold simultaneously for the adjacency spectral radius and the signless Laplacian spectral radius.
  • The new bounds apply to graphs that are less tough than the classical 1/(k-2) threshold of Win but still satisfy the intermediate toughness floor.

Where Pith is reading between the lines

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

  • As t grows, the toughness floor t/(t(k-2)+1) increases toward 1/(k-2), suggesting a possible sequence of successively stronger sufficient conditions that approach Win's original threshold.
  • The spectral bounds are likely sharp for certain families of graphs that achieve equality in the toughness definition, so explicit extremal constructions could be examined to test tightness.
  • The same technique might extend to other bounded-degree spanning subgraphs or to k-trees with additional connectivity requirements.

Load-bearing premise

The graph is connected and its toughness is at least t/(t(k-2)+1) for the chosen integer t.

What would settle it

A connected graph whose toughness equals exactly t/(t(k-2)+1), whose order lies below the stated bound, and whose spectral radius lies below the stated bound, yet still contains no spanning k-tree, would falsify the claim.

read the original abstract

The toughness of a graph $G$, denoted by $\tau(G)$, is defined by $\tau(G)=$min $\{\frac{|S|}{c(G-S)}:S\subseteq V(G)$ and $c(G-S)\geq2\}$. A graph $G$ is said to be $\tau$-tough if $\tau(G)\geq \tau$. Let $k\geq2$ be an integer. A tree $T$ is called a $k$-tree if $d_{T}(v)\leq k$ for each $v\in V(T)$, that is, the maximum degree of a $k$-tree is at most $k$. A $k$-tree $T$ is a spanning $k$-tree if $T$ is a spanning subgraph of a connected graph $G$. In 1989, Win [Graphs Combin. 5 (1989) 201--205] proved that if $\tau(G)\geq\frac{1}{k-2}$, where $k\geq3$, then $G$ contains a spanning $k$-tree. Liu, Fan and Shu [Discrete Math. 348 (2025) 114593] provided a tight sufficient condition based on the spectral condition for connected $\frac{1}{k}$-tough and $\frac{1}{k-1}$-tough graphs to contain a spanning $k$-tree, where $k\geq3$ is an integer. A natural and interesting problem arises: Can the value of $\tau$ be refined? When $\frac{1}{k-2}>\tau\geq\frac{1}{k-1}$, we initially establish a lower bound on the size to ensure that a connected $\frac{t}{t(k-2)+1}$-tough graph $G$ contains a spanning $k$-tree, where $k\geq3$ and $t\geq1$ are integers. Meanwhile, we provide two sufficient conditions in terms of spectral radius and signless Laplacian spectral radius for a connected $\frac{t}{t(k-2)+1}$-tough graph $G$ to contain a spanning $k$-tree, where $k\geq3$ and $t\geq1$ are integers. When $t=1$, we obtain the result $\eta=1$ from Liu, Fan and Shu.

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

0 major / 4 minor

Summary. The paper claims to provide sufficient conditions for spanning k-trees in connected graphs with a parameterized toughness τ = t/(t(k-2)+1) for integers k≥3, t≥1. Specifically, such graphs contain a spanning k-tree if their order is at least some bound or if their spectral radius or signless Laplacian spectral radius exceeds a certain threshold. This refines Win's theorem for toughness 1/(k-2) and matches Liu et al. at t=1.

Significance. If correct, this work is significant as it fills the gap in toughness values between 1/(k-1) and 1/(k-2) by using a discrete family parameterized by t, and incorporates modern spectral graph theory tools to give alternative sufficient conditions. It builds directly on prior results and could inspire further refinements in toughness-based extremal problems.

minor comments (4)
  1. [Abstract] The sentence 'When 1/(k-2)>τ≥1/(k-1), we initially establish a lower bound on the size...' could be clarified by specifying what the lower bound is or referring to the theorem number.
  2. [Abstract] The mention of 'the result η=1' is unclear without context; ensure that any auxiliary parameter η is defined in the main text and its relation to the toughness is explained.
  3. [Introduction] Add a brief discussion on the sharpness of the new toughness threshold and whether there are known examples showing that smaller toughness does not guarantee the spanning k-tree even with large order.
  4. [Main theorems] Verify that the spectral conditions are stated with explicit constants or bounds in terms of k and t.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation for minor revision. No specific major comments were provided in the report, so we have no point-by-point responses to address. We will implement minor revisions to improve clarity, notation, and presentation in the next version of the manuscript.

Circularity Check

0 steps flagged

No significant circularity; extends independent prior theorems

full rationale

The derivation extends Win's 1989 toughness threshold and the 2025 Liu-Fan-Shu spectral conditions to the discrete family of intermediate toughness values τ = t/(t(k-2)+1) for integer t ≥ 1. All load-bearing steps cite these external results as black-box inputs, then apply standard toughness-to-degree-component arguments followed by spectral-radius comparison against known extremal non-k-tree graphs. When t=1 the statement recovers the cited Liu-Fan-Shu theorem verbatim rather than re-deriving it; no equation defines a parameter from data internal to this paper and then renames that parameter as a prediction. The argument chain therefore remains self-contained against the cited external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of toughness, the definition of a k-tree, and the assumption that the graph is connected. No new free parameters are fitted to data; k and t are given integers. No new entities are postulated. The paper invokes standard graph-theoretic background results (e.g., basic properties of trees and eigenvalues) whose proofs lie outside the present work.

axioms (1)
  • standard math Basic properties of finite undirected graphs, trees, and the toughness function as defined in the paper
    Invoked throughout the statements and implicitly in any proof extending Win's theorem.

pith-pipeline@v0.9.0 · 5727 in / 1306 out tokens · 57432 ms · 2026-05-07T06:39:15.122197+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

29 extracted references · 29 canonical work pages

  1. [1]

    Chen, J.X

    H.Z. Chen, J.X. Li, S.J. Xu, Two variants of toughness of a graph and its eigenvalues, Graphs Combin. 41 (2025) 41

    work page 2025

  2. [2]

    Chv´ atal, Tough graphs and Hamiltonian circuits, Discrete Math

    V. Chv´ atal, Tough graphs and Hamiltonian circuits, Discrete Math. 5 (1973) 215–228

    work page 1973

  3. [3]

    Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math

    K. Das, Maximizing the sum of the squares of the degrees of a graph, Discrete Math. 285 (2004) 57–66

    work page 2004

  4. [4]

    Egawa, M

    Y. Egawa, M. Furuya, The existence of a path-factor without small odd paths, Electron. J. Combin. 25 (2018) #P1.40

    work page 2018

  5. [5]

    Ellingham, X.Y

    M.N. Ellingham, X.Y. Zha, Toughness, trees, and walks, J. Graph Theory. 33 (2000) 125–137

    work page 2000

  6. [6]

    D.D. Fan, S. Goryainov, X.Y. Huang, H.Q. Lin, The spanningk-trees, perfect matchings and spectral radius of graphs, Linear Multilinear Algebra. 70 (2022) 7264–7275

    work page 2022

  7. [7]

    Fan, H.Q

    D.D. Fan, H.Q. Lin, H.L. Lu, Toughness, hamiltonicity and spectral radius in graphs, European J. Combin. 110 (2023) 103701

    work page 2023

  8. [8]

    Hong, A bound on the spectral radius of graphs, Linear Algebra Appl

    Y. Hong, A bound on the spectral radius of graphs, Linear Algebra Appl. 108 (1988) 135–139

    work page 1988

  9. [9]

    Johansson, An El-Zah´ ar type condition ensuring path-factors, J

    R. Johansson, An El-Zah´ ar type condition ensuring path-factors, J. Graph Theory. 28 (1998) 39–42

    work page 1998

  10. [10]

    Johnson, D

    M. Johnson, D. Paulusma, C. Wood, Path factors and parallel knock-out schemes of almost claw-free graphs, Discrete Math. 310 (2010) 1413–1423

    work page 2010

  11. [11]

    Kano, G.Y

    M. Kano, G.Y. Katona, Z. Kir´ aly, Packing paths of length at least two, Discrete Math. 283 (2004) 129–135

    work page 2004

  12. [12]

    S. Kim, S. O, J. Park, H. Ree, An odd [1, b]-factor in regular graphs from eigenvalues, Discrete Math. 343 (2020) 111906

    work page 2020

  13. [13]

    M. Kano, A. Saito, Star-factors with large components, Discrete Math. 312 (2012) 2005– 2008

    work page 2012

  14. [14]

    Q. Li, K.Q. Feng, On the largest eigenvalue of a graph, Acta Math. Appl. Sinica. 2 (1979) 167–175

    work page 1979

  15. [15]

    R.F. Liu, A. Fan, J.L. Shu, Spectral extremal problems on factors in tough graphs, and beyond, Discrete Math. 348 (2025) 114593

    work page 2025

  16. [16]

    Liu, X.G

    H.X. Liu, X.G. Pan, Independence number and minimum degree for path-factor critical uniform graphs, Discrete Appl. Math. 359 (2024) 153–158

    work page 2024

  17. [17]

    Liu, W.C

    R.F. Liu, W.C. Shiu, J. Xue, Sufficient spectral conditions on Hamiltonian and trace- ablegraphs, Linear Algebra Appl. 467 (2015) 254–266

    work page 2015

  18. [18]

    Liu, J.F

    G.Z. Liu, J.F. Wang, (a, b, k)-critical graphs, Adv. Math. (China) 27 (1998) 536–540. 10

    work page 1998

  19. [19]

    Lv, A degree condition for graphs being fractional (a, b, k)-critical covered, Filomat

    X.Y. Lv, A degree condition for graphs being fractional (a, b, k)-critical covered, Filomat. 37 (2023) 3315–3320

    work page 2023

  20. [20]

    Matsuda, Fan-type results for the existence of [a, b]-factors, Discrete Math

    H. Matsuda, Fan-type results for the existence of [a, b]-factors, Discrete Math. 306 (2006) 688–693

    work page 2006

  21. [21]

    B. Ning, J. Ge, Spectral radius and Hamiltonian properties of graphs, Linear Multilinear Algebra. 63 (2015) 1520–1530

    work page 2015

  22. [22]

    Shen, L.H

    Y. Shen, L.H. You, M.J. Zhang, S.C. Li, On a conjecture for the signless Laplacian spec- tral radius ofcacti with given matching number, Linear Multilinear Algebra. 65 (2017) 457–474

    work page 2017

  23. [23]

    Wang, M.K

    T. Wang, M.K. Yang, X.J. Yang, Signless Laplacian spectral conditions fork-critical graphs with respect to [1, b]-odd factors, Graphs Combin. 41 (2025) 125

    work page 2025

  24. [24]

    Win, On a connection between the existence ofk-trees and the toughness of a graph, Graphs Combin

    S. Win, On a connection between the existence ofk-trees and the toughness of a graph, Graphs Combin. 5 (1989) 201–205

    work page 1989

  25. [25]

    Zhou, A neighborhood union condition for fractional (a, b, k)-critical covered graphs, Discrete Appl

    S.Z. Zhou, A neighborhood union condition for fractional (a, b, k)-critical covered graphs, Discrete Appl. Math. 323 (2022) 343–348

    work page 2022

  26. [26]

    Zhou, H.X

    S.Z. Zhou, H.X. Liu, Two sufficient conditions for odd [1, b]-factors in graphs, Linear Algebra Appl. 661 (2023) 149–162

    work page 2023

  27. [27]

    Zhou, J.C

    S.Z. Zhou, J.C. Wu, Spanningk-trees and distance spectral radius in graphs, J. Super- comput. 80 (2024) 23357–23366

    work page 2024

  28. [28]

    S.Z. Zhou, Y. Xu, Z.R. Sun, Some results about star-factors in graphs, Contrib. Discrete Math. 19 (2024) 154–162

    work page 2024

  29. [29]

    Zhou, Y.L

    S.Z. Zhou, Y.L. Zhang, H.X. Liu, Spanningk-trees and distance signless Laplacian spec- tral radius of graphs, Discrete Appl. Math. 358 (2024) 358–365. 11

    work page 2024