A spectral condition for Hamilton cycles in tough bipartite graphs
Lianyang Ai, Wenqian Zhang* · 2025
Read A spectral condition for Hamilton cycles in tough bipartite graphs by Lianyang Ai, Wenqian Zhang* (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-2508-03778.txt.
Introduction
Ai and Zhang give a sharp spectral condition for Hamilton cycles in tough balanced bipartite graphs, in a paper from twenty twenty-five. A Hamilton cycle visits every vertex exactly once and returns. Spectral radius, the largest adjacency eigenvalue, can certify such cycles. Bipartite toughness measures how hard a graph is to split apart.
For balanced bipartite graphs with toughness at least one, they find the exact spectral threshold. Above it, a Hamilton cycle is guaranteed to exist. At the threshold, the extremal structure is pinned down as well. The result settles an open problem posed in prior work. It links eigenvalue bounds and toughness in a tight, complete way.
Catalog record
| CREATOR | Lianyang Ai, Wenqian Zhang* |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 16 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-03778
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A spectral condition for Hamilton cycles in tough bipartite graphs Lianyang Ai, Wenqian Zhang* Abstract Let G G be a graph. The spectral radius of G G is the largest eigenvalue of its adjacency matrix. For a non-complete bipartite graph G G with parts X X and Y Y , the bipartite toughness of G G is defined as t B ( G ) = min { | S | c ( G − S ) } t^{B}(G)=\min\left\{\frac{|S|}{c(G-S)}\right\} , where the minimum is taken over all proper subsets S ⊂ X S\subset X (or S ⊂ Y S\subset Y ) such that c ( G − S ) > 1 c(G-S)>1 . In this paper, we give a sharp spectral radius condition for balanced bipartite graphs G G with t B ( G ) ≥ 1 t^{B}(G)\geq 1 to guarantee that G G contains Hamilton cycles. This solves a problem proposed in [ 9 ] . Keywords: spectral radius; Hamilton cycle; bipartite graph; [ a , b ] [a,b] -factor. 2020 Mathematics Subject Classification: 05C50. † † footnotetext: * Corresponding author † † footnotetext: E-mails: [email protected], [email protected] 1 Introduction All graphs considered here are finite, undirected and simple. For a graph G , let V(G) and E(G) denote the vertex set and edge set of G , respectively. Let e(G)=|E(G)| . For a vertex u , let d_{G}(u) denote its degree. Let \delta(G) be the minimum degree of G . For a subset S of V(G) , let G[S] be the subgraph induced by S , and let G-S obtained from G by deleting the vertices in S and the incident edges. For two disjoint subsets U and V of V(G) , let e_{G}(U,V) be the number of edges between U and V . For certain integers m,n , let K_{n} and K_{m,n} denote the complete graph and the complete bipartite graph, respectively. The spectral radius of G is the largest eigenvalue of its adjacency matrix. For any terminology used but not defined here, one may refer to [ 3 ] . Let G be a graph. For non-negative integers a and b , an [a,b] -factor of G is a spanning subgraph with degrees between a and b . An [a,b] -factor is called a k -factor if a=b=k . Recently, many researchers studied the spectral radius conditions for graphs to contain [a,b] -factors (for example, see [ 8 , 9 , 12 , 13 , 14 , 15 , 16 , 21 , 22 ] ). A Hamilton cycle of G is a connected 2 -factor. Recently, many researchers studied the spectral radius conditions for graphs to contain Hamilton cycles (for example, see [ 2 , 10 , 11 , 17 , 18 , 19 , 20 , 23 , 24 ] ). Chvátal [ 7 ] defined the toughness t(G) of a non-complete graph G as t(G)=\min\left\{\frac{|S|}{c(G-S)}\right\} , where the minimum is taken over all proper subsets S\subset V(G) , and c(G-S) denotes the number of components of G-S . We say that G is k -tough, if t(G)\geq k . Clearly, if G has a Hamiltonian cycle then G is 1-tough. Conversely, Chvátal [ 7 ] proposed the following conjecture. Conjecture. ( [ 7 ] ) There exists a constant C such that every C -tough graph is Hamiltonian. Bauer, Broersma and Veldman [ 1 ] constructed examples which implies that C\geq\frac{9}{4} (if it exists). In general, this conjecture still remains open. For n\geq 8 , denote the vertex set of K_{n-3} by \left\{v_{1},v_{2},...,v_{n-3}\right\} . Let M_{n} be the graph obtained from K_{n-3} by adding 3 vertices u_{1},u_{2},u_{3} (all) connecting to v_{1} , and connecting u_{i} to v_{i+1} for any 1\leq i\leq 3 . Clearly, M_{n} is a 1-tough graph of order n . Note that M_{n} contains no Hamilton cycles, since the three vertices u_{1},u_{2},u_{3} are of degree 2 and have a common neighbor v_{1} . Fan, Lin and Lu [ 11 ] proposed the problem: What is the spectral condition to guarantee the existence of a Hamiltonian cycle among t -tough graphs? They proved the following result. Theorem 1.1 Suppose that G is a connected 1-tough graph of order n\geq 18 (with \delta(G)\geq 2 ). If \rho(G)\geq\rho(M_{n}) , then G contains a Hamiltonian cycle, unless G=M_{n} . Let G=G(X,Y) denote a bipartite graph with parts X and Y , where |X|\leq|Y| . The graph G is balanced if |X|=|Y| . Observe that t(G)\leq 1 , since G-X has |Y| components. Bian [ 6 ] introduced the concept of bipartite toughness for G . For a non-complete bipartite graph G , its bipartite toughness t^{B}(G) is defined as t^{B}(G)=\min\left\{\frac{|S|}{c(G-S)}\right\} , where the minimum is taken over all proper subsets S\subset X (or S\subset Y ) such that c(G-S)>1 . We say that G is k -tough, if t^{B}(G)\geq k . For n\geq 5 , denote the two parts of K_{n,n-3} by \left\{u_{1},u_{2},...,u_{n}\right\} and \left\{v_{4},v_{5},...,v_{n}\right\} . Let G_{n,n} be the graph obtained from K_{n,n-3} by adding 3 vertices v_{1},v_{2},v_{3} (all) connecting to u_{1} , and connecting v_{i} to u_{i+1} for any 1\leq i\leq 3 . Clearly, G_{n,n} is a 1-tough balanced bipartite graph of order 2n . Note that G_{n,n} contains no 2-factors, since the three vertices v_{1},v_{2},v_{3} are of degree 2 and have a common neighbor u_{1} . Chen, Fan and Lin [ 9 ] proved the following result. Theorem 1.2 ( [ 9 ] ) Suppose that G is a connected 1-tough balanced bipartite graph of order 2n . If \rho(G)\geq\rho(G_{n,n}) , then G contains a 2-factor, unless G=G_{n,n} . At the end of [ 9 ] , the authors guessed that G contains a Hamilton cycle in the condition of Theorem 1.2 . In this paper, we confirm this. Theorem 1.3 Let G=G(X,Y) be a 1-tough balanced bipartite graph of order 2n , where |X|=|Y|=n\geq 16 . If \rho(G)\geq\rho(G_{n,n}) , then G contains a Hamilton cycle, unless G=G_{n,n} . 2 Proof of Theorem 1.3 To prove Theorem 1.3 , we first include some lemmas. Lemma 2.1 ( [ 3 ] ) Let G be a connected graph. For any subgraph H of G , \rho(H)\leq\rho(G) with equality if and only if H=G . Lemma 2.2 ( [ 5 ] ) If G is a bipartite graph, then \rho(G)\leq\sqrt{e(G)} . Moreover, equality holds if and only if G is a complete bipartite graph with some isolated vertices. Let G=G(X,Y) be a balanced bipartite graph of order 2n . The bipartite closure H of G , is the graph obtained from G by recursively joining pairs of non-adjacent vertices u\in X and v\in Y satisfying d_{G}(u)+d_{G}(v)\geq n+1 until no such pair remains. The following is the bipartite closure technique, which is widely used in the study of Hamilton cycles in balanced bipartite graphs. Theorem 2.3 ( [ 4 ] ) A balanced bipartite graph G is Hamiltonian if and only if its bipartite closure is Hamiltonian. Now we begin the proof of Theorem 1.3 . Proof of Theorem 1.3 : Since G is 1-tough, we see \delta(G)\geq 2 . Let H be the bipartite closure of G . Then H is a 1-tough balanced bipartite graph. Note that G is