In this paper, we investigate the well-studied Hamiltonian cycle problem, and present an interesting dichotomy result on split graphs. T. Akiyama, T. Nishizeki, and N. Saito [23] have shown that the Hamiltonian cycle problem is NP-complete in planar bipartite graph with maximum degree 3. Using this reduction, we show that the Hamiltonian cycle problem is NP-complete in split graphs. In particular, we show that the problem is NP-complete in K_(1,5)-free split graphs. Further, we present polynomial-time algorithms for Hamiltonian cycle in K_(1,3)-free and K_(1,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 and other variants of Hamiltonian cycle problem.
展开▼
机译：在本文中，我们调查了学习的哈密顿循环问题，并在分裂图上呈现了一个有趣的二分法结果。 T. Akiyama，T. Nishizeki和N. Saito [23]已经表明，Hamiltonian循环问题是在平面二分的图中完成最高3.使用这种减少，我们表明Hamiltonian循环问题是NP-Cression在拆分图中。特别是，我们表明问题是k_（1,5）-free拆分图中的np-complete。此外，我们在k_（1,3）-free和k_（1,4）中呈现Hamiltonian循环的多项式时间算法。 - 免费拆分图。我们认为本文提出的结构结果可用于显示汉密尔顿道路和汉密尔顿循环问题的其他变体的类似二分法结果。
展开▼
