The Hamiltonian Cycle in K_1,r-free Split Graphs -- A Dichotomy

2016/10/04 by P. Renjith, Renjith, P., N. Sadagopan +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1610.00855

openalex publication_date 2016/10/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 in planar bipartite graphs with maximum degree 3. Using this reduction, we show that HCYCLE 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 problem (HPATH) and other variants of HCYCLE.

Citations

• Tough graphs and hamiltonian circuits
• Long cycles in graphs with prescribed toughness and minimum degree

Cited by

• Short Cycles Decide P-versus-NPC Status ofHamiltonicity on Bisplit Graphs

Related

• Hamiltonian Path in Split Graphs- a Dichotomy
• Hamiltonian path and Hamiltonian cycle are solvable in polynomial time in graphs of bounded independence number
• On the Structure of Hamiltonian Graphs with Small Independence Number
• Hamiltonian Cycle Problem is in P
• NP-Completeness of Hamiltonian Cycle Problem on Rooted Directed Path Graphs