Tight spectral conditions for the Hamiltonicity of K 1 , r K_{1,r} -free split graphs
Yiting Cai, Haiyan Guo, Hong-Jian Lai, Bo Zhou · 2026
Read Tight spectral conditions for the Hamiltonicity of K 1 , r K_{1,r} -free split graphs by Yiting Cai, Haiyan Guo, Hong-Jian Lai, Bo Zhou (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-14763.txt.
Introduction
Cai, Guo, Lai, and Zhou give tight spectral conditions for K-one-r-free split graphs to be Hamiltonian when r equals 3 or 4. Dai and coauthors conjectured every (r-minus-one)-connected K-one-r-free split graph is Hamiltonian, with r equals 4 and r equals 3 already proved. A recent result says a split graph is Hamiltonian exactly when fully cycle extendable, so those connected cases are fully cycle extendable too. The new conditions pin down, in spectral terms, when such graphs hold a Hamiltonian cycle.
Catalog record
| CREATOR | Yiting Cai, Haiyan Guo, Hong-Jian Lai, Bo Zhou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103277 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.14763
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tight spectral conditions for the Hamiltonicity of K 1 , r K_{1,r} -free split graphs Yiting Cai, Haiyan Guo, Hong-Jian Lai, Bo Zhou Abstract The Hamiltonicity and related subjects of split graphs, and in particular K 1 , r K_{1,r} -free split graphs with r ≥ 3 r\geq 3 received much attention. Dai et al. [Discrete Math. 345 (2022) 112826] conjectured that every ( r − 1 ) (r-1) -connected K 1 , r K_{1,r} -free split graph is Hamiltonian. They proved the case when r = 4 r=4 , and earlier Renjith and Sadagopan [Int. J. Found. Comput. Sci. 33 (2022) 1–32] proved the case when r = 3 r=3 . Recently, Liu, Song, Zhang and Lai [Discrete Math. 346 (2023) 113402] proved that a split graph is Hamiltonian if and only if it is fully cycle extendable. So for r = 3 , 4 r=3,4 every ( r − 1 ) (r-1) -connected K 1 , r K_{1,r} -free split graph is fully cycle extendable. We give tight spectral sufficient conditions for a K 1 , r K_{1,r} -free split graph to be Hamiltonian for r = 3 , 4 r=3,4 . Keywords: K 1 , r K_{1,r} -free graphs, split graphs, Hamiltonian graphs, Hamiltonian problem, spectral radius AMS Classification: 05C45, 05C40, 05C50 1 Introduction In this paper, we consider only finite simple graphs. A graph G is Hamiltonian if it contains a Hamiltonian cycle, i.e., a cycle contains all vertices of G . A graph is Hamilton-connected if for every pair of distinct vertices u,v , there exists a Hamiltonian path (a path containing all vertices) from u to v . A graph is fully cycle extendable if every vertex lies on a cycle of length 3 and for every non-hamiltonian cycle C there is a cycle C^{\prime} such that |V(C^{\prime})|=|V(C)|+1 and V(C)\subset V(C^{\prime}) . A graph G is a split graph if the vertex set V(G) can be partitioned into a clique K and an independent set I , either of which may be empty. The clique can be chosen to be a maximum clique, and in such case, we say that G is of type (K,I) , and write G=(K,I) if there is no confusion. Split graphs were introduced by Foldes and Hammer [ 8 ] in 1977, and were studied further in [ 2 , 9 , 10 , 12 , 13 , 14 ] . A split graph G=(K,I) is said to be complete if any vertex of K is adjacent all vertices of I . An obvious necessary condition that a split graph G=(K,I) is Hamiltonian is |K|\geq|I| . Let r be an integer with r\geq 3 . A graph G is K_{1,r} -free if G does not have an induced subgraph isomorphic to K_{1,r} , that is, no vertex of G has r pairwise nonadjacent neighbors. A K_{1,3} -free graph is known as a claw-free graph. The Hamiltonicity of claw-free graphs received much attention, see, e.g. [ 3 , 4 , 5 , 6 ] . Renjith and Sadagopan [ 13 ] and Dai, Zhang, Broerama and Zhang [ 7 ] showed the following results. Theorem 1.1 . [ 13 ] Let G=(K,I) be a claw-free split graph. Then G is Hamiltonian if and only if G is 2 -connected. Theorem 1.2 . [ 7 ] Every 3 -connected K_{1,4} -free split graph is Hamiltonian. After proving Theorem 1.2 , Dai, Zhang, Broerama and Zhang [ 7 ] proposed the following conjecture, which is true for r=3,4 (by Theorems 1.1 and 1.2 ). Conjecture 1.1 . [ 7 ] Every (r-1) -connected K_{1,r} -free split graph is Hamiltonian. Liu, Song, Zhang and Lai [ 11 ] studied the Hamilton-connectedness and fully cycle extendability of K_{1,r} -free split graphs. Let r=3,4 . They showed that a r -connected K_{1,r} -free split graph is Hamilton-connected, and as an immediate consequence of the claim that a split graph is Hamiltonian if and only if it is fully cycle extendable, every (r-1) -connected K_{1,r} -free split graph is fully cycle extendable. The spectral radius \rho(M) of a square (complex) matrix M the largest modulus of the eigenvalues of M . Let A(G) be the adjacency mattrix of G , where A(G)=(a_{uv})_{u,v\in V(G)} with a_{uv}=1 if u and v are adjacent and 0 otherwise. The spectral radius of a graph G is defined as \rho(G)=\rho(A(G)) . For integers n and t with 1\leq t\leq\frac{n}{2} and n\geq 4 , let G_{n,t} be the graph obtained from K_{n-t}\cup tK_{1} V(tK_{1})=\{u_{1},\dots,u_{t}\} and V(K_{n-t})=\{v_{1},\dots,v_{n-t}\} by adding edges u_{i}v_{i} for all i=1,\dots,\max\{t-1,1\} and u_{t}v_{j} for all j=t,\dots,n-t and t\geq 2 , see Fig. 1 . K_{n-1} G_{n,1} u_{1} v_{1} tK_{1} K_{n-t} G_{n,t}~(t\geq 2) Figure 1 : Graphs G_{n,t} . Theorem 1.3 . Let G=(K,I) be a connected claw-free split graph of order n , where n\geq\max\{4,2|I|\} . If \rho(G)\geq\rho(G_{n,|I|}), then G is Hamiltonian, unless G\cong G_{n,|I|} . An immediate consequence of the previous theorems is as follows. Corollary 1.1 . Let G=(K,I) be a connected claw-free split graph of order n , where n\geq\max\{4,2|I|\} . If \rho(G)\geq\rho(G_{n,|I|}), then G is 2 -connected, unless G\cong G_{n,|I|} . To state the result for K_{1,4} -free split graphs, we need further notation. First, we define the graphs \Gamma_{n,t} for 1\leq t\leq\frac{n}{2} and n\geq 5 . Let \Gamma_{n,1}=G_{n,1} . For t\geq 2 , we define a split graph \Gamma_{n,t}=(K,I) with I=\{u_{1},\dots,u_{t}\} and K=\{v_{1},\dots,v_{n-t}\} as follows. In \Gamma_{n,2} , the edges between K and I are u_{1}v_{i} for all i=1,\dots,n-3 and u_{2}v_{n-3} . In \Gamma_{n,3} , the edges between K and I are u_{i}v_{j} for all i=1,2 and j=1,\dots,n-4 and u_{3}v_{n-3} . In \Gamma_{n,4} , the edges between K and I are u_{i}v_{j} for all i=1,2 and j=1,\dots,n-5 , u_{3}v_{k} for all k=2,\dots,n-4 , and u_{4}v_{n-4} . In \Gamma_{n,5} , the edges between K and I are u_{1}v_{1} , u_{1}v_{n-5} , u_{i}v_{j} for all i=2,3 and j=1,\dots,n-6 , u_{4}v_{k} for all k=2,\dots,n-5 , and u_{5}v_{n-5} . For 6\leq t\leq\lfloor\frac{n}{2}\rfloor , in \Gamma_{n,t} , the edges between K and I are u_{i}v_{i} for all i=1,\dots,t-5 , u_{t-4}v_{j} for all j=1,\dots,n-t-1 , u_{t-3}v_{k} for all k=1,\dots,n-t-2,n-t , u_{t-2}v_{\ell} for all \ell=t-4,\dots,n-t , u_{t-1}v_{n-t-1} and u_{t}v_{n-t} . See Fig. 2 for \Gamma_{n,t} with t\geq 2 . K_{n-2} \Gamma_{n,2} \Gamma_{n,3} K_{n-3} K_{n-4} \Gamma_{n,4} K_{n-5} \Gamma_{n,5} tK_{1} K_{n-t} \Gamma_{n,t} with t\geq 6 Figure 2 : Graphs \Gamma_{n,t} with t\geq 2 . Next, let \Gamma_{n,2}^{\prime} and \Gamma_{n,3}^{\prime} be the n -vertex graphs (K,I) with |I|=2,3\leq\frac{n}{2} , given in Fig. 3 , where \Gamma_{n,2}^{\prime} is the graph obtained from K_{n-2}\cup 2K_{1} with V(2K_{1})=\{u_{1},u_{2}\} and V(K_{n-2})=\{v_{1},\dots,v_{n-2}\} by adding edges u_{i}v_{j} for all i,j=1,2 , and \Gamma_{n,3}^{\prime} is the graph obtained from K_{n-3}\cup 3K_{1} with V(3K_{1})=\{u_{1},u_{2},u_{3}\} and V(K_{n-3})=\{v_{1},\dots,v_{n-3}\} by adding edges u_{i}v_{j} for all i,j=1,2 and u_{3}v_{k} for all k=2,\dots,n-3 . K_{n-2} \Gamma_{n,2}^{\prime} K_{n-3} \Gamma_{n,3}^{\prime} Figure 3 : Graphs \Gamma_{n,2}^{\prime},\Gamma_{n,3}^{\prime} . Theorem 1.4 . Let G=(K,I) be a connected K_{1,4} -free split graph of order n\geq\max\{5,2|I|\} . If \rho(G)\geq\begin{cases}\rho(\Gamma_{n,2}^{\prime})&\mbox{if~}|I|=2,n=5\\ \rho(\Gamma_{n,3}^{\prime})&\mbox{if~}|I|=3,n=6\\ \rho(\Gamma_{n,|I|})&\mbox{otherwise}\end{cases} then G is Hamiltonian, unless G\cong\begin{cases}\Gamma_{n,2}^{\prime}&\mbox{if~}|I|=2,n=5,\\ \Gamma_{n,3}^{\prime}&\mbox{if~}|I|=3,n=6,\\ \Gamma_{n,|I|}&\mbox{otherwise}.\end{cases} Very recently, Zhu et al. [ 15 ] gave a spectral condition to imply a connected split graph (K,I) with certain constraints on |K| and |I| is Hamiltonian. For positive integers p and q , let