Hamiltonian Path in Split Graphs- a Dichotomy

2017/11/25 by P. Renjith, Renjith, P., N. Sadagopan +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1711.09262

openalex publication_date 2017/11/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Related

• The Hamiltonian Cycle in K_1,r-free 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