1-tough cocomparability graphs are hamiltonian

DOI10.1016/0012-365X(95)00359-5zbMath0876.05066MaRDI QIDQ1363656

Dieter Kratsch, George Steiner, Jitender S. Deogun

Publication date: 10 August 1997

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

cocomparability graphsHamilton cyclescattering numberpath cover number1-tough cocomparability graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45)

Related Items

Cyclability in graph classes ⋮ The scattering number of strictly chordal graphs: linear time determination ⋮ Toughness and Hamiltonicity in \(k\)-trees ⋮ The scattering number of thorn graphs ⋮ Toughness, hamiltonicity and split graphs ⋮ Characterization of interval graphs that are unpaired 2-disjoint path coverable ⋮ Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs ⋮ Disjoint path covers joining prescribed source and sink sets in interval graphs ⋮ Toughness and Hamiltonicity of strictly chordal graphs ⋮ Assistance and interdiction problems on interval graphs ⋮ Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs ⋮ Unnamed Item ⋮ Vulnerability of subclasses of chordal graphs ⋮ On Toughness and Hamiltonicity of 2K₂‐Free Graphs ⋮ Some properties of \(k\)-trees ⋮ Toughness in graphs -- a survey ⋮ Unnamed Item ⋮ Chvátal’s t 0-Tough Conjecture ⋮ Hamiltonian powers in threshold and arborescent comparability graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Long cycles in graphs with large degree sums
• An optimum \(\Theta\) (n log n) algorithm for finding a canonical Hamiltonian path and a canonical Hamiltonian circuit in a set of intervals
• Recognizing tough graphs is NP-hard
• Finding Hamiltonian circuits in interval graphs
• Computing the bump number is easy
• Computing the bump number with techniques from two-processor scheduling
• Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
• On a class of posets and the corresponding comparability graphs
• On the complexity of recognizing tough graphs
• Hamiltonicity in graphs with few \(P_ 4\)'s
• Hamiltonian degree conditions for tough graphs
• An optimal path cover algorithm for cographs
• Toughness, hamiltonicity and split graphs
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors
• An $O(n^2 \log n)$ Algorithm for the Hamiltonian Cycle Problem on Circular-Arc Graphs
• On Maximal Circuits in Finite Graphs
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs