Hamiltonian Path in K_(1,t)-free Split Graphs-A Dichotomy

摘要

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. That is, unless P = NP, Hamiltonian path problem has no polynomial-time solution in K_(1,5)-free split graphs and polynomial-time solvable in K_(1,4)-free split graphs.