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]表明，在平面二分图中，汉密尔顿循环问题是NP完全的，最大程度为3。使用这种减少，我们证明了汉密尔顿循环问题是NP-完全的在拆分图中。特别地，我们表明问题在无K_（1,5）的分裂图中是NP完全的。此外，我们在无K_（1,3）和无K_（1,4）分裂图中提出了哈密顿循环的多项式时间算法。我们认为，本文介绍的结构结果可用于显示汉密尔顿路径和汉密尔顿循环问题的其他变体的相似二分法结果。
展开▼
