Hamiltonian Path in Split Graphs- a Dichotomy

11/25/2017

∙

by   P. Renjith, et al.

∙

0

∙

share

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.