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

DOI10.1007/978-3-319-74180-2_3MaRDI QIDQ2636552zbMATH OpenOpenAlexFDO

Authors P. Renjith, N. Sadagopan

Publication date 5 June 2018

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

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)

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.

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

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)