Hamiltonicity in Split Graphs - A Dichotomy

DOI10.1007/978-3-319-53007-9_28zbMath1485.68199arXiv1610.00855OpenAlexW2529351937MaRDI QIDQ2971662

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

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

Related Items

Injective coloring of some subclasses of bipartite graphs and chordal graphs, Hamiltonian Cycle in K1,r-Free Split Graphs — A Dichotomy, Short cycles dictate dichotomy status of the Steiner tree problem on bisplit graphs, Domination and its variants in split graphs \(-\text{P}\) versus NPC dichotomy, THE DOMINATION GAME ON SPLIT GRAPHS, Some algorithmic results on Hamiltonicity and its variants in \(P_6\)-free graphs

Cites Work

• Improved degree conditions for Hamiltonian properties
• General solutions to the single vehicle routing problem with pickups and deliveries
• Finding Hamiltonian circuits in interval graphs
• Hamiltonian circuits in interval graph generalizations
• A note on Hamiltonian split graphs
• Hamiltonian circuits determining the order of chromosomes
• Advances on the Hamiltonian problem -- a survey
• On some intriguing problems in Hamiltonian graph theory---a survey
• The P versus NP-complete dichotomy of some challenging problems in graph theory
• Long cycles in graphs with prescribed toughness and minimum degree
• Toughness, hamiltonicity and split graphs
• HAMILTONian circuits in chordal bipartite graphs
• On the Burkard-Hammer condition for Hamiltonian split graphs
• Tough graphs and Hamiltonian circuits.
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
• Complexity of Steiner Tree in Split Graphs - Dichotomy Results
• Connected (s,t)-Vertex Separator Parameterized by Chordality
• Updating the hamiltonian problem—A survey
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Unnamed Item