Sufficient conditions for spanning k k -trees in tough graphs This work is supported by the National Natural Science Foundations of China (Nos. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632), High-Quality Science and Technology Cultivation Project of Jiangsu Normal University (No. JSNUGZL2026069).

Caili Jia, Yong Lu · 2026

Read Sufficient conditions for spanning k k -trees in tough graphs This work is supported by the National Natural Science Foundations of China (Nos. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632), High-Quality Science and Technology Cultivation Project of Jiangsu Normal University (No. JSNUGZL2026069). by Caili Jia, Yong Lu (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-27908.txt.

Introduction

Jia and Lu chase sharper toughness rules for spanning k-trees, which cap links at k per vertex and touch every vertex. Win showed in 1989 that toughness of at least one over k minus two forces a tree. Liu, Fan, and Shu gave a tight 2025 spectral rule. Jia and Lu fill that gap. They prove a size floor guaranteeing the tree at a toughness level set by t. They add spectral-radius and signless-Laplacian tests. At t equal to one, it returns.

Catalog record

CREATORCaili Jia, Yong Lu
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20523
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2604.27908

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sufficient conditions for spanning k k -trees in tough graphs This work is supported by the National Natural Science Foundations of China (Nos. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632), High-Quality Science and Technology Cultivation Project of Jiangsu Normal University (No. JSNUGZL2026069). Caili Jia, Yong Lu Abstract 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)\geq 2\} . A graph G is said to be \tau -tough if \tau(G)\geq\tau . Let k\geq 2 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\geq 3 , 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\geq 3 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\geq 3 and t\geq 1 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\geq 3 and t\geq 1 are integers. When t=1 , we obtain the result \eta=1 from Liu, Fan and Shu. Keywords : Toughness; Spectral radius; Signless Laplacian spectral radius; Spanning k -tree. AMS Subject Classification (2020) : 05C35; 05C50. 1 Introduction Throughout this paper, we consider only finite, undirected and simple graphs. Let G=(V(G),E(G)) be a graph, where V(G) is the vertex set and E(G) is the edge set. The order and size of G are denoted by |V(G)|=n and |E(G)|=e(G) , respectively. We denote by d_{G}(v) the degree of v\in V(G) . Denote by c(G) the number of components of a graph G . Let G_{1} and G_{2} be two disjoint graphs. The union G_{1}\cup G_{2} is the graph with vertex set V(G_{1})\cup V(G_{2}) and edge set E(G_{1})\cup E(G_{2}) . The join G_{1}\vee G_{2} is derived from G_{1}\cup G_{2} by joining every vertex of G_{1} with every vertex of G_{2} by an edge. Let G be a graph of order n , and let the adjacency matrix of G be defined as A(G)=(a_{ij})_{n\times n} , where a_{ij}=1 if v_{i}v_{j}\in E(G) , and a_{ij}=0 otherwise. The degree diagonal matrix is the diagonal matrix of vertex degrees of G , denoted by D(G) . The signless Laplacian matrix Q(G) of G is defined by Q(G)=D(G)+A(G) . The eigenvalues of A(G) and Q(G) are called the eigenvalues and the signless Laplacian eigenvalues of G , and denoted by \rho_{1}(G)\geq\rho_{2}(G)\geq\cdots\geq\rho_{n}(G) and q_{1}(G)\geq q_{2}(G)\geq\cdots\geq q_{n}(G) , respectively. The largest eigenvalues of A(G) and Q(G) are also called the spectral radius and the signless Laplacian spectral radius of G , and denoted by \rho(G) and q(G) , respectively. For two integers a and b such that 0\leq a\leq b , a spanning subgraph F of G is called an [a,b] -factor if a\leq d_{F}(v)\leq b for each v\in V(G) . If a=1 , then an [a,b] -factor is a [1,b] -factor. If b=1 , then a [1,b] -factor is a 1 -factor or a perfect matching. Let k\geq 2 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 . It is obvious that G admits a spanning k -tree if and only if G admits a connected [1,k] -factor. The study of spanning k -trees and [a,b] -factors has received extensive attention from scholars. Some sufficient conditions for graphs with [1,2] -factors were obtained by many researchers [ 4 , 9 , 10 , 11 , 16 , 23 ] . Kim et al. [ 12 ] , Kano and Saito [ 13 ] , Zhou, Xu and Sun [ 28 ] showed some results for the existence of [1,b] -factors in graphs. Zhou and Liu [ 26 ] studied the relationship between the spectral radius of a connected graph and its odd [1,b] -factors, and claimed a lower bound on the existence of odd [1,b] -factors via the spectral radius. Many scholars investigated the properties of [a,b] -factors in graphs, and provided some graphic parameter conditions for graphs having [a,b] -factors [ 19 , 18 , 20 , 25 ] . A graph G is \tau -tough if |S|\geq\tau\cdot c(G-S) for every subset S\subseteq V(G) with c(G-S)\geq 2 , where c(G) is the number of components of a graph G . The toughness \tau(G) of G is the maximum \tau for which G is \tau -tough (taking \tau(K_{n})=\infty ). Hence if G is not a complete graph, \tau(G)= min \{\frac{|S|}{c(G-S)}\} where the minimum is taken over all cut sets of vertices in G . This concept was first introduced by Chvátal [ 2 ] as a way of measuring how tightly various pieces of a graph hold together. Chvátal proposed the following conjecture. Conjecture 1.1 . [ 2 ] Here exists a finite constant \tau_{0} such that every \tau_{0} -tough graph is Hamiltonian. Fan, Lin and Lu [ 7 ] initially presented a tight sufficient condition in terms of the spectral radius for a connected 1 -tough graph to contain a connected Hamilton cycle. One naturally considers the following problem: Problem 1.2 . [ 15 ] What is a tight spectral condition to guarantee the existence of factors among tough graphs? Win [ 24 ] proved that if \tau(G)\geq\frac{1}{k-2} with k\geq 3 , then G contains a spanning k -tree. Lemma 1.3 . [ 24 ] [ 5 ] Let k\geq 3 be an integer. If a connected graph G satisfies \displaystyle c(G-S)\leq(k-2)|S|+2, for any vertex subset S of G , then G admits a spanning k -tree. In 1989 , Win [ 24 ] (see also [ 5 ] for a short proof) proved a sufficient condition for the existence of a spanning k -tree in a connected graph. Lots of scholars presented some sufficient spectral conditions for graphs to possess spanning k -tree. Since a spanning 2 -tree is just a Hamilton path, Ning and Ge [ 21 ] provide such condition for k=2 in terms of the adjacency spectral radius. In [ 17 ] , Liu, Shiu and Xue gave a signless Laplacian spectral radius for the existence of a Hamilton path in a connected graph. For any k\geq 3 , Fan et al. [ 6 ] presented a lower bound on the spectral radius of a connected graph G

Read the complete text