pith. sign in

arxiv: 2604.14763 · v1 · submitted 2026-04-16 · 🧮 math.CO

Tight spectral conditions for the Hamiltonicity of K_(1,r)-free split graphs

Yiting Cai , Haiyan Guo , Hong-Jian Lai , Bo Zhou This is my paper

Pith reviewed 2026-05-10 11:08 UTC · model grok-4.3

classification 🧮 math.CO
keywords split graphsHamiltonicityspectral radiusK_{1,r}-free graphscycle extendabilityadjacency eigenvaluestight conditions
0
0 comments X

The pith

Tight spectral radius bounds suffice to guarantee Hamiltonicity for K_{1,3}-free and K_{1,4}-free split graphs.

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

The paper supplies explicit spectral conditions on the adjacency matrix that force a K_{1,r}-free split graph to contain a cycle through every vertex, for the cases r=3 and r=4. Earlier theorems showed that (r-1)-connectivity already guarantees Hamiltonicity in this class, via the equivalence of Hamiltonicity with full cycle extendability in all split graphs. Spectral conditions therefore provide an alternative, often more readily computable, certificate that replaces direct connectivity checks. A reader would care because the bounds are stated to be tight, meaning they cannot be relaxed without admitting non-Hamiltonian examples inside the same family.

Core claim

For r=3 and r=4 the authors derive explicit lower bounds on the largest eigenvalue of the adjacency matrix such that any K_{1,r}-free split graph meeting the bound must be Hamiltonian. The conditions are shown to be sharp by reference to extremal graphs that attain the bound yet remain non-Hamiltonian, and the proofs combine the known connectivity-to-Hamiltonicity results with standard spectral techniques that bound the size of independent sets or the structure of the split partition.

What carries the argument

The largest eigenvalue (spectral radius) of the adjacency matrix of the graph, used to enforce a minimum degree or connectivity threshold that triggers the known Hamiltonicity criterion for split graphs.

If this is right

  • Any K_{1,3}-free split graph whose spectral radius meets the r=3 threshold is Hamiltonian.
  • Any K_{1,4}-free split graph whose spectral radius meets the r=4 threshold is Hamiltonian.
  • The spectral conditions imply that the graphs are fully cycle extendable, inheriting all the cycle-extension properties already known for Hamiltonian split graphs.
  • The same eigenvalue bounds serve as practical certificates that can replace explicit connectivity verification for this restricted class.

Where Pith is reading between the lines

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

  • The same style of spectral bound could be tested for larger r where the connectivity conjecture remains open.
  • Because the conditions are eigenvalue-based, they may be easier to verify numerically than combinatorial connectivity for moderately large instances.
  • The extremal graphs used to show tightness may themselves suggest new families of non-Hamiltonian split graphs whose spectra can be computed exactly.

Load-bearing premise

That the stated eigenvalue threshold is large enough to force the graph to satisfy the (r-1)-connectivity condition already known to imply Hamiltonicity.

What would settle it

Exhibit a single K_{1,r}-free split graph on n vertices whose largest adjacency eigenvalue meets or exceeds the claimed threshold yet contains no Hamiltonian cycle.

Figures

Figures reproduced from arXiv: 2604.14763 by Bo Zhou, Haiyan Guo, Hong-Jian Lai, Yiting Cai.

Figure 1
Figure 1. Figure 1: Graphs Gn,t. Theorem 1.3. Let G = (K, I) be a connected claw-free split graph of order n, where n ≥ max{4, 2|I|}. If ρ(G) ≥ ρ(Gn,|I|), then G is Hamiltonian, unless G ∼= Gn,|I| . 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Graphs Γn,t with t ≥ 2. Next, let Γ′ n,2 and Γ′ n,3 be the n-vertex graphs (K, I) with |I| = 2, 3 ≤ n 2 , given in [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Graphs Γ′ n,2 , Γ ′ n,3 . then G is Hamiltonian, unless G ∼=    Γ ′ n,2 if |I| = 2, n = 5, Γ ′ n,3 if |I| = 3, n = 6, Γn,|I| otherwise. 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 S(1, p, 1, q) be the split graph G = (K, I) with |K| = 1 + p and |I| = 1 + q in … view at source ↗
Figure 4
Figure 4. Figure 4: The structure of G in the proof of Theorem 1.3. and ρ(G)xj = (dG(uj ) − 1)xj + X |I| k=1 k̸=j dG(uk)xk + [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: The structure of Γ′′ n,2 . Lemma 4.1. For n ≥ 6, let Γ ′′ n,2 be the graph displayed in [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: The structure of Γ′′ n,3 . Lemma 4.3. Let Γ ′ n,4 be the graph displayed in [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: The structure of Γ′ n,4 . Lemma 4.4. Let Γ ′ n,5 and Γ ′′ n,5 be two graphs displayed in [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The structures of Γ′ n,5 and Γ′′ n,5 . Lemma 4.5. Let Γ ∗ n,|I| and Γ ∗∗ n,|I| be two graphs displayed in [PITH_FULL_IMAGE:figures/full_fig_p008_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The structures of Γ∗ n,|I| and Γ∗∗ n,|I| . Let Gn be the class of n-vertex split graphs of type (K, I) each of which is connected, K1,4-free, and not Hamiltonian. Lemma 4.6. Let G = (K, I) be a connected K1,4-free split graph of order n ≥ 2|I| that is not Hamilto￾nian but with maximum spectral radius, where |I| ≥ 4. If there exists a vertex of K such that its degree in I is equal to 3, then there is a vert… view at source ↗
Figure 10
Figure 10. Figure 10: The structure of Γ. Let V1 = NG(u2) ⊆ K′ , V2 = K′ \ V1, V3 = K′′ , V4 = {u : u ∈ I \ {u1, u2}, NG(u) ∈ V2} and V5 = I \ ({u1, u2} ∪ V4), where |V5| = 2|K′′|, |V4| = |I| − |V5| − 2, and |V4| = 0 if |I| = 2|K′′| + 2. By symmetry, denote by xi the entry of x at each vertex from Vi for i = 1, . . . , 5. Note that (ρ(Γ) + 1)(x1 − x3) = xu1 + xu2 − 2x5, ρ(Γ)(xu1 − x5) = |V1|x1 + |V2|x2 − x3 and ρ(Γ)(xu2 − x5) … view at source ↗
Figure 11
Figure 11. Figure 11: The structure of Γ′ . If there are exactly two vertices of I with degree 2, then the neighborhood of them are the same as G is not Hamiltonian, so G ∼= Γ ′ n,3 with n ≥ 7. By Lemma 4.2, we have ρ(G) < ρ(Γn,3), a contradiction. Suppose in the following that |I| ≥ 4 (in Case 2). By Lemma 4.6, there is a vertex of I with degree 1. As xu1 ≥ xu2 ≥ xu3 , we have dG(u2) = dG(u3) = 1 if dG(u1) = 1, contradicting … view at source ↗
Figure 12
Figure 12. Figure 12: The structure of G. Then we claim that dI (v11) ≤ 2, as otherwise, to avoid K1,4, one vertex of NI (v11) \ {u1} is adjacent to v21, contradicting the fact that ∆(B) = 1. So |I| = 4 and G has the structure as displayed in [PITH_FULL_IMAGE:figures/full_fig_p016_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The structure of Γ. So B33 ̸= ∅. Then B33 ⊂ NG(u4) by Claim 4.7. Then A11∪B22 = ∅, as otherwise G−u4v1+u3v1 ∈ Gn, and by Lemma 2.2 in view of xu3 ≥ xu4 , ρ(G − u4v1 + u3v1) > ρ(G), a contradiction. Note that |B| = 1, as otherwise |B| ≥ 2, then G − u4v31 + u1v31 ∈ Gn, and by Lemma 2.2, ρ(G − u4v31 + u1v31) > ρ(G), a contradiction. By Lemma 4.6, we have G ∼= Γn,5. Suppose next that A13 ̸= ∅. Let A13 = {v2},… view at source ↗
read the original abstract

The Hamiltonicity and related subjects of split graphs, and in particular $K_{1,r}$-free split graphs with $r\ge 3$ received much attention. Dai et al. [Discrete Math. 345 (2022) 112826] conjectured that every $(r-1)$-connected $K_{1,r}$-free split graph is Hamiltonian. They proved the case when $r=4$, and earlier Renjith and Sadagopan [Int. J. Found. Comput. Sci. 33 (2022) 1--32] proved the case when $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$ every $(r-1)$-connected $K_{1,r}$-free split graph is fully cycle extendable. We give tight spectral sufficient conditions for a $K_{1,r}$-free split graph to be Hamiltonian for $r=3,4$.

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 / 2 minor

Summary. The manuscript establishes tight spectral sufficient conditions for the Hamiltonicity of K_{1,r}-free split graphs when r=3 and r=4. It reduces the problem to known structural theorems (that every (r-1)-connected K_{1,r}-free split graph is Hamiltonian, in fact fully cycle extendable) by proving that the stated lower bounds on the spectral radius force the graph to satisfy the required minimum-degree or connectivity condition on the split partition, using standard Rayleigh-quotient or degree-sequence arguments. Tightness is witnessed by explicit infinite families of non-Hamiltonian examples whose spectral radii approach the proposed thresholds from below.

Significance. If the derivations hold, the paper supplies concrete, falsifiable spectral criteria that directly translate structural Hamiltonicity results into eigenvalue language for a well-studied subclass of split graphs. The explicit thresholds for each r and the matching infinite families of extremal examples constitute a genuine strengthening of the existing literature on spectral Hamiltonicity. The reduction via standard tools (Rayleigh quotients on the clique-independent-set partition) is clean and proportionate to the claim.

minor comments (2)
  1. The abstract states that 'tight spectral sufficient conditions' are given but does not record the explicit numerical thresholds; adding the precise bounds (one for r=3, one for r=4) would improve immediate readability.
  2. In the tightness constructions, confirm that the limit of the spectral radii is stated with the same normalization (e.g., divided by n or not) as the sufficient-condition bound itself.

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 appear in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation reduces Hamiltonicity of K_{1,r}-free split graphs to the known structural theorem that every (r-1)-connected such graph is Hamiltonian (or equivalently fully cycle extendable), by proving via Rayleigh quotients and degree-sequence arguments that the stated spectral-radius lower bound forces the required minimum degree or connectivity. This spectral implication step is independent of the structural input and uses standard tools; the cited structural results (including one with author overlap) are prior independent theorems, not self-definitions or fits. No equation or claim reduces to its own input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only the abstract is available, so the precise free parameters, axioms, and invented entities cannot be audited; the paper appears to rely on standard finite simple undirected graph axioms and previously established structural theorems.

axioms (1)
  • standard math Graphs are finite, simple, and undirected.
    Implicit background assumption for all results in the abstract.

pith-pipeline@v0.9.0 · 5503 in / 1115 out tokens · 46084 ms · 2026-05-10T11:08:02.768160+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

20 extracted references · 20 canonical work pages

  1. [1]

    Brualdi, E.S

    R.A. Brualdi, E.S. Solheid, On the spectral radius of connected graphs, Publ. Inst. Math. (Beograd) (N.S.) 39 (53) (1986) 45–54

    work page 1986

  2. [2]

    Burkazd, P.L

    R.E. Burkazd, P.L. Hammer, A note on Hamiltonian split graphs, J. Comb. Theory, Ser. B 28 (1980) 245–248

    work page 1980

  3. [3]

    Chen, Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs II, Discrete Math

    Z.-H. Chen, Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs II, Discrete Math. 345 (7) (2022) 112642

    work page 2022

  4. [4]

    Chen, Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs, Discrete Math

    Z.-H. Chen, Hamiltonicity and restricted degree conditions on induced subgraphs in claw-free graphs, Discrete Math. 344 (1) (2021) 112165

    work page 2021

  5. [5]

    Chen, Hamiltonicity of claw-free graphs and Fan-type conditions, Discrete Math

    Z.-H. Chen, Hamiltonicity of claw-free graphs and Fan-type conditions, Discrete Math. 342 (4) (2019) 1066–1078

    work page 2019

  6. [6]

    Chen, H.-J

    Z.-H. Chen, H.-J. Lai, L. Xiong, Minimum degree conditions for the Hamiltonicity of 3-connected claw-free graphs, J. Combin. Theory Ser. B 122 (2017) 167—186

    work page 2017

  7. [7]

    G. Dai, Z. Zhang, H. Broersma, X. Zhang, The Hamiltonian properties inK 1,r-free split graphs, Discrete Math. 345 (2022) 112826. 23

    work page 2022

  8. [8]

    Foldes, P.L

    S. Foldes, P.L. Hammer, Split graphs, in: Proceedings of the 8th South-Eastern Conference on Combinatorics, Graph Theory and Computing, 1977, pp. 311–315

    work page 1977

  9. [9]

    Foldes, P.L

    S. Foldes, P.L. Hammer, Split graphs having Dilworth number two, Can. J. Math. 24 (1977) 666– 672

    work page 1977

  10. [10]

    Kratsch, J

    D. Kratsch, J. Lehel, H. Muller, Toughness, hamiltonicity and split graphs, Discrete Math. 150 (1996) 231–245

    work page 1996

  11. [11]

    X. Liu, S. Song, M. Zhan, H.-J. Lai, On hamiltonian properties ofK 1,r-free split graphs, Discrete Math. 346 (2023) 113402

    work page 2023

  12. [12]

    Merris, Split graphs, Eur

    R. Merris, Split graphs, Eur. J. Combin. 24 (2003) 413–430

    work page 2003

  13. [13]

    Renjith, N

    P. Renjith, N. Sadagopan, The Hamiltonian cycle inK 1,r-free split graphs – a dichotomy, Int. J. Found. Comput. Sci. 33 (2022) 1–32

    work page 2022

  14. [14]

    Tan, L.X

    N.D. Tan, L.X. Hung, On the Burkard-Hammer condition for Hamiltonian split graphs, Discrete Math. 296 (2005) 59–72

    work page 2005

  15. [15]

    Y. Zhu, D. Fan, H. Lin, Spectral radius and hamiltonicity in split graphs, Discrete Math. 348 (2025) 114624. Appendix A Proof of Lemma 4.1 Proof.LetI={u 1, u2}andV(K n−2) ={v 1, . . . , vn−2}in Γ ′ n,2 and Γ′′ n,2. We first show thatρ(Γn,2)> ρ(Γ ′′ n,2). LetN Γ′′ n,2(u2) ={v n−2}. Thenv i ∈N Γ′′ n,2(u1) fori= 1, . . . , n−3. Denote byxthe Perron vector of...

    work page 2025

  16. [16]

    =az ′ 1 + (n−2a−7)z ′ 2 >0 andρ(G ′)(z′ 7 −z ′

    work page

  17. [17]

    Note thatρ(Γ ∗ n,|I|)(x7 −x 8) =x 3

    = (n−2a−7)z ′ 2 +z ′ 3 >0, we havez ′ 5 −z ′ 6 >0 andz ′ 7 −z ′ 6 >0. Note thatρ(Γ ∗ n,|I|)(x7 −x 8) =x 3. Then z′⊤ ρ(G′)−ρ(Γ ∗ n,|I|) x = X v∈V2\{v2} (xvz′ v5 +x 5zv −x vz′ v7 −x 7zv) +x 3z′ v8 +x 8z′ v3 −x 3z′ v7 −x 7z′ v3 = (n−2a−7)(x 2z′ 5 +x 5z′ 2 −x 2z′ 6 −x 7z′

    work page

  18. [18]

    +x 3z′ 7 +x 8z′ 3 −x 3z′ 6 −x 7z′ 3 = (n−2a−7)(x 2(z′ 5 −z ′

    work page

  19. [19]

    + (x8 −x 7)z′ 3 = (n−2a−7)(x 2(z′ 5 −z ′

    work page

  20. [20]

    Thusρ(Γ n,|I|)> ρ(Γ ∗ n,|I|) asG ′ ∼= Γn,|I|

    + n−2a−7 ρ(G′) x3z′ 2 + 1 ρ(G′) − 1 ρ(Γ∗ n,|I|) ! x3z′ 3, i.e., ρ(G′)−ρ(Γ ∗ n,|I|) z′⊤x+ x3z′ 3 ρ(G′)ρ(Γ∗ n,|I|) ! >0, soρ(G ′)> ρ(Γ ∗ n,|I|). Thusρ(Γ n,|I|)> ρ(Γ ∗ n,|I|) asG ′ ∼= Γn,|I|. 29

    work page