Sufficient conditions for t t -tough graphs to be Hamiltonian and pancyclic or bipartite This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX25_3155), the Postgradua
Xiangge Liu, Caili Jia, Yong Lu, Jiaxu Zhong · 2025
Read Sufficient conditions for t t -tough graphs to be Hamiltonian and pancyclic or bipartite This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX25_3155), the Postgradua by Xiangge Liu, Caili Jia, Yong Lu, Jiaxu Zhong (2025) 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-2505-11090.txt.
Introduction
Xiangge Liu and co-authors settle a graph theory metaconjecture for tough graphs in a 2025 paper. A graph's toughness measures how hard it is to shatter by removing points. Bondy once guessed that almost any condition forcing a ring through all points, a Hamiltonian cycle, also forces rings of every length. For graphs of toughness one, two, or three that guess was recently confirmed using size and spectral measures.
This paper covers toughness four and above. Five measures get the treatment: plain size, two matrix spectra tied to connections, and two more built from distances. In each case, a strong enough condition yields rings of all lengths, or the graph splits into two camps with no edges within, the allowed exception. A fifty-year-old hunch gains another brick.
Catalog record
| CREATOR | Xiangge Liu, Caili Jia, Yong Lu, Jiaxu Zhong |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-11090
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 t t -tough graphs to be Hamiltonian and pancyclic or bipartite This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX25_3155), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632, 2025XKT0633) . Xiangge Liu, Caili Jia, Yong Lu, Jiaxu Zhong Abstract Abstract The toughness of graph G , denoted by \tau(G) , is \tau(G)=\min\{\frac{|S|}{c(G-S)}:S\subseteq V(G),c(G-S)\geq 2\} for every vertex cut S of V(G) and the number of components of G is denoted by c(G) . Bondy in 1973, suggested the “metaconjecture” that almost any nontrivial condition on a graph which implies that the graph is Hamiltonian also implies that the graph is pancyclic. Recently, Benediktovich [Discrete Applied Mathematics. 365 (2025) 130–137] confirmed the Bondy’s metaconjecture for t -tough graphs in the case when t\in\{1;2;3\} in terms of the size, the spectral radius and the signless Laplacian spectral radius of the graph. In this paper, we will confirm the Bondy’s metaconjecture for t -tough graphs in the case when t\geq 4 in terms of the size, the spectral radius, the signless Laplacian spectral radius, the distance spectral radius and the distance signless Laplacian spectral radius of graphs. Key Words : Touhgness; Hamiltonian; Pancyclic; Spectra of graphs. AMS Subject Classification (2010) : 05C35; 05C50. 1 Introduction Let G=(V(G),E(G)) be a simple 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)|=m , respectively. For a vertex subset S of G , we denote by G-S and G[S] the subgraph of G obtained from G by deleting the vertices in S together with their incident edges and the subgraph of G induced by S , respectively. Let t be a positive real number and a connected graph G is t -tough if tc(G-S)\leq|S| for every vertex cut S of V(G) and the number of components of G is denoted by c(G) . The toughness of graph G , denoted by \tau(G) , is \tau(G)=\min\{\frac{|S|}{c(G-S)}:S\subseteq V(G),c(G-S)\geq 2\} for every vertex cut S of V(G) (taking \tau(K_{n})=\infty ). This concept was initially proposed by Chvátal [ 11 ] in 1973, which serves as a simple way to measure how tightly various pieces of a graph hold together. Let d(v) be the degree of vertex v\in V(G) , \delta(G) (or \Delta(G) ) be the minimum degree (or maximum degree ) of G and short for \delta (or \Delta ). We denote the cycle and the complete graph on n vertices by using C_{n} and K_{n} , respectively. For two vertex-disjoint graphs G_{1} and G_{2} , we use G_{1}+G_{2} to denote the disjoint union of G_{1} and G_{2} . The join G_{1}\vee G_{2} is the graph obtained from G_{1}+G_{2} by adding all possible edges between V(G_{1}) and V(G_{2}) . If G_{1}=G_{2}=\cdots=G_{k} , we denote G_{1}+G_{2}+\cdots+G_{k} by kG_{1} . A graph G is called Hamiltonian if it has a cycle that contains all vertices of G , and pancyclic if it has simple cycles of all lengths from 3 to n . A pancyclic graph is certainly Hamiltonian, but not conversely in general. We denote a bipartite graph with bipartition (X,Y) by using G[X,Y] , and a complete bipartite graph with two parts having m,n vertices by using K_{m,n} . For a simple graph G of order n , the adjacency matrix of G is denoted by A(G) , and \lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G) are the eigenvalues of A(G) . In particular, the eigenvalue \lambda_{1}(G) is called the spectral radius of G . The distance between v_{i} and v_{j} denoted by d_{ij}(G) , is the length of a shortest path from v_{i} to v_{j} , and the distance matrix of G is the symmetric matrix D(G)=(d_{ij}(G))_{n\times n} with its rows and columns indexed by V(G) . We can order the eigenvalues of D(G) as \lambda_{1}(D(G))\geq\lambda_{2}(D(G))\geq\cdots\lambda_{n}(D(G)) where the distance spectral radius of G is \lambda_{1}(D(G)) . The matrix Q(G)=D^{\prime}(G)+A(G) , where D^{\prime}(G) is a degree diagonal matrix of G , is called the signless Laplacian matrix of G and the largest eigenvalue of Q(G) , denoted by q(G) , is called to be the signless Laplacian spectral radius . The transmission Tr(v) of a vertex v\in V(G) is the sum of distances from v to all vertices in G . We say that a graph is k -transmission-regular (or transmission-regular) if its distance matrix has constant row sum equal to k . The distance signless Laplacian matrix of a graph G , is given by Q_{D}(G)=Diag(Tr)+D(G) , where Diag(Tr) is the diagonal matrix whose diagonal entries are the vertex transmissions in G . Let \eta_{1}(G)\geq\eta_{2}(G)\geq\cdots\geq\eta_{n}(G) be eigenvalues of Q_{D}(G) and the largest eigenvalue \eta_{1}(G) is also called the distance signless Laplacian spectral radius . Many researchers established the relationship between toughness conditions and the spectra of graphs. Fan et al. [ 14 ] presented sufficient conditions based on the spectral radius for graphs to be 1-tough with minimum degree \delta(G) and graphs to be t -tough with t\geq 1 being an integer, respectively. Lou et al. [ 22 ] presented a sufficient condition based on the distance spectral radius to guarantee that a graph is t -tough, where t or \frac{1}{t} is a positive integer. Jia and Lou [ 19 ] also considered the above problem based on the signless Laplacian spectral radius. For more extensive work on toughness conditions related to the spectra of graphs, one can see ( [ 6 ] , [ 8 ] , [ 9 ] , [ 10 ] ). Meanwhile, the study of Hamiltonian, pancyclic and the spectra of graphs has received extensive attention. In 1972, Erdős [ 13 ] conjectured that every Hamiltonian graph with independence number at most k and at least n=\Omega(k^{2}) vertices is pancyclic. Draganić et al. [ 12 ] proved this conjecture in a strong form. Zhou and Wang [ 33 ] established some sufficient conditions for a graph to be Hamilton-connected in terms of the size, the spectral radius and the signless Laplacian spectral radius of the graph. They [ 32 ] also considered the relationship between distance signless Laplacian spectral radius and the Hamiltonian properties of graphs according to the size m and the order n . For more extensive work on Hamiltonian, pancyclic and the spectra of graphs, one can see ( [ 15 ] , [ 21 ] , [ 27 ] , [ 31 ] , [ 34 ] ). Chvátal and other scholars investigated the relationship between toughness conditions and the existence of cyclic structures, in particular, determining whether the graph is Hamiltonian or pancyclic. It is well-known that recognition problems whether the graph is Hamiltonian or pancyclic are NP-complete. Cai et al. [ 7 ] established sufficient conditions for a tough graph G to be Hamiltonian based on the size, the spectral radius and the signless Laplacian spectral radius. Fan et al. [ 14 ] also presented sufficient conditions for tough graphs to be Hamiltonion in terms of the spectral radius. As is well known, if a graph G with n\geq 3 , and every vertex has minimum degree at least \frac{n}{2} , then