{"id":"arxiv/2607.27802","url":"https://arxiv.org/abs/2607.27802","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Short Cycles Decide P-versus-NPC Status ofHamiltonicity on Bisplit Graphs","domain":"cs.DM","source":"arxiv","authors":["Mahendra Kumar R","Renjith P","Aadhavan S","Sadagopan N"],"reviews":0,"subject":"cs.DM","summary":"A connected graph G is said to be a bisplit graph if the vertex set of G can be partitioned into a stable set and a complete bipartite graph. We establish the following dichotomy with chordality being the parameter; for chordal bisplit graphs, Hamiltonian cycle (HCYCLE) and Hamiltonian path (HPATH) problems are polynomial-time solvable, and for chordal bipartite bisplit graphs, HCYCLE (HPATH) is NP-complete. We further strengthen the result of [1] and show that HCYCLE (HPATH) is polynomial-time solvable on P5-free chordal bipartite graphs (bipartite chain graphs) and NP-complete on P10-free…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}