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)

Full work available at URL https://doi.org/10.1016/0012-365X(95)00359-5

zbMATH Keywords

1-tough cocomparability graphcocomparability graphsHamilton cyclepath cover numberscattering number

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

• 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
• scientific article; zbMATH DE number 867682 (Why is no real title available?)
• Long cycles in graphs with large degree sums
• On a class of posets and the corresponding comparability graphs
• On Maximal Circuits in Finite 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

(25)

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

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)