Title: Hamiltonian Path in Split Graphs- a Dichotomy,
Abstract: In this paper, we investigate Hamiltonian path problem in the context of
split graphs, and produce a dichotomy result on the complexity of the problem.
Our main result is a deep investigation of the structure of $K_{1,4}$-free
split graphs in the context of Hamiltonian path problem, and as a consequence,
we obtain a polynomial-time algorithm to the Hamiltonian path problem in
$K_{1,4}$-free split graphs. We close this paper with the hardness result: we
show that, unless P=NP, Hamiltonian path problem is NP-complete in
$K_{1,5}$-free split graphs by reducing from Hamiltonian cycle problem in
$K_{1,5}$-free split graphs. Thus this paper establishes a "thin complexity
line" separating NP-complete instances and polynomial-time solvable instances.