1-tough cocomparability graphs are hamiltonian

DOI10.1016/0012-365X(95)00359-5MaRDI QIDQ1363656zbMATH OpenFDO

Authors Jitender Deogun, Dieter Kratsch, George Steiner

Publication date 10 August 1997

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

cocomparability graphsHamilton cyclepath cover numberscattering number1-tough cocomparability graph

Mathematics Subject Classification ID

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

Recommendations

• A sufficient condition for Hamiltonian cycles in tough graphs
• Forbidden subgraphs for Hamiltonicity of 1-tough graphs
• 10-tough chordal graphs are Hamiltonian (extended abstract)
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• 10-tough chordal graphs are Hamiltonian

Cites work

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

Cited in

(23)

• Toughness in graphs -- a survey
• scientific article; zbMATH DE number 2230266 (Why is no real title available?)
• Toughness and Hamiltonicity in k-trees
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• The scattering number of strictly chordal graphs: linear time determination
• Toughness and Hamiltonicity of strictly chordal graphs
• Hamiltonian powers in threshold and arborescent comparability graphs
• Hamiltonicity of 1-tough \((P_2 \cup KP_1)\)-free graphs
• Characterization of interval graphs that are unpaired 2-disjoint path coverable
• Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
• scientific article; zbMATH DE number 861334 (Why is no real title available?)
• Assistance and interdiction problems on interval graphs
• The scattering number of thorn graphs
• Hamiltonian cycles in 7-tough \((P_3 \cup 2P_1)\)-free graphs
• Some properties of \(k\)-trees
• Semi-proper interval graphs
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• More relations between \(\lambda \)-labeling and Hamiltonian paths with emphasis on line graph of bipartite multigraphs
• Toughness, hamiltonicity and split graphs
• On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
• Chvátal's \(t_{0}\)-tough conjecture
• Cyclability in graph classes
• Vulnerability of subclasses of chordal graphs

This page was built for publication: 1-tough cocomparability graphs are hamiltonian

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