Hamiltonian path in K₁,t-free split graphs -- a dichotomy

DOI10.1007/978-3-319-74180-2_3zbMATH Open1497.68394arXiv1711.09262OpenAlexW2783228594MaRDI QIDQ2636552FDOQ2636552

Authors: P. Renjith, N. Sadagopan 

Publication date: 5 June 2018

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.

Full work available at URL: https://arxiv.org/abs/1711.09262

Recommendations

• Hamiltonicity in Split Graphs - A Dichotomy
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• On Hamiltonian properties of \(K_{1, r}\)-free split graphs
• On the Hamiltonian and classification problems for some families of split graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Cited In (4)

• Hamiltonicity in Split Graphs - A Dichotomy
• A closer look at Hamiltonicity and domination through the lens of diameter and convexity
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• Impact of diameter and convex ordering for Hamiltonicity and domination

This page was built for publication: Hamiltonian path in \(K_{1,t}\)-free split graphs -- a dichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2636552)