Hamiltonian Cycle in K1,r-Free Split Graphs - A Dichotomy

For an optimization problem known to be NP-Hard, the dichotomy study investigates the reduction instances to determine the line separating polynomial-time solvable vs NP-Hard instances (easy vs hard instances). In this paper, we investigate the well-studied Hamiltonian cycle problem (HCYCLE), and present an interesting dichotomy result on split graphs. T. Akiyama et al. (1980) have shown that HCYCLE is NP-complete on planar bipartite graphs with maximum degree 3. We use this result to show that HCYCLE is NP-complete for K-1,K-5-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in K-1,K-3-free and K-1,K-4-free split graphs. We believe that the structural results presented in this paper can be used to show similar dichotomy result for Hamiltonian path problem and other variants of Hamiltonian cycle (path) problems.