Open Research Index

Short Cycles Decide P-versus-NPC Status ofHamiltonicity on Bisplit Graphs

Mahendra Kumar R, Renjith P, Aadhavan S, Sadagopan N

arXivarxiv/2607.27802Jul 30, 2026cs.DMscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2607.27802
curl -X POST /api/v1/records/arxiv/2607.27802/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.27802/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'