Hamiltonicity in Split Graphs - A Dichotomy

DOI10.1007/978-3-319-53007-9_28MaRDI QIDQ2971662zbMATH OpenOpenAlexFDO

Authors P. Renjith, N. Sadagopan

Publication date 7 April 2017

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05) Eulerian and Hamiltonian graphs (05C45)

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.

Recommendations

• On the Hamiltonian and classification problems for some families of split graphs
• On the Burkard-Hammer condition for Hamiltonian split graphs
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• On Hamiltonian properties of \(K_{1, r}\)-free split graphs
• Hamiltonian path in \(K_{1,t}\)-free split graphs -- a dichotomy
• The Hamiltonian properties in \(K_{1,r}\)-free split graphs
• Toughness, hamiltonicity and split graphs
• Hamilton cycles in split graphs with large minimum degree
• Partitioning graphs into Hamiltonian ones
• On Hamiltonian bipartite graphs

Cites work

• scientific article; zbMATH DE number 3694608 (Why is no real title available?)
• A note on Hamiltonian split graphs
• Advances on the Hamiltonian problem -- a survey
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• Complexity of Steiner tree in split graphs -- dichotomy results
• Connected (s,t)-vertex separator parameterized by chordality
• Finding Hamiltonian circuits in interval graphs
• General solutions to the single vehicle routing problem with pickups and deliveries
• HAMILTONian circuits in chordal bipartite graphs
• Hamiltonian circuits determining the order of chromosomes
• Hamiltonian circuits in interval graph generalizations
• Improved degree conditions for Hamiltonian properties
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Long cycles in graphs with prescribed toughness and minimum degree
• On some intriguing problems in Hamiltonian graph theory---a survey
• On the Burkard-Hammer condition for Hamiltonian split graphs
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Tough graphs and Hamiltonian circuits.
• Toughness, hamiltonicity and split graphs
• Updating the hamiltonian problem—A survey

Cited in

(10)

• Injective coloring of some subclasses of bipartite graphs and chordal graphs
• Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs
• scientific article; zbMATH DE number 3857154 (Why is no real title available?)
• THE DOMINATION GAME ON SPLIT GRAPHS
• Hamiltonian path in \(K_{1,t}\)-free split graphs -- a dichotomy
• Advances in Aharoni-Hartman-Hoffman's conjecture for split digraphs
• Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy
• Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy
• Hamilton cycles in split graphs with large minimum degree
• Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs

This page was built for publication: Hamiltonicity in Split Graphs - A Dichotomy

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