On the complexity of recognizing tough graphs

DOI10.1016/0012-365X(92)00047-UMaRDI QIDQ1313820zbMATH OpenFDO

Authors D. Bauer, Aurora Morgana, E. Schmeichel

Publication date 10 March 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)00047-U

zbMATH Keywords

Hamiltonian graphNP-hardtough graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• The complexity of recognizing minimally tough graphs
• scientific article; zbMATH DE number 6770058
• Recognizing tenacious graphs is NP-hard.
• Recognizing tough graphs is NP-hard
• The complexity of recognizing tough cubic graphs

Cites work

• Graph theory
• scientific article; zbMATH DE number 3912424 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Long Cycles in Digraphs
• Long cycles in graphs with large degree sums
• Recognizing tough graphs is NP-hard
• Some Theorems on Abstract Graphs
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors

Cited in

(23)

• 1-tough cocomparability graphs are hamiltonian
• The complexity of recognizing tough cubic graphs
• Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
• Independence free graphs and vertex connectivity augmentation
• Recognizing brittle graphs: Remarks on a paper of Hoàng and Khouzam
• A note on the approximability of the toughness of graphs
• Properties of minimally \(t\)-tough graphs
• Toughness in graphs -- a survey
• The complexity of recognizing minimally tough graphs
• Stability theorems for graph vulnerability parameters
• On the minimum degree of minimally 1-tough, triangle-free graphs and minimally 3/2-tough, claw-free graphs
• Various results on the toughness of graphs
• On Path-Tough Graphs
• Toughness and vertex degrees
• Forbidden Induced Subgraphs for Toughness
• ON THE HARDNESS OF RECOGNIZING BUNDLES IN TIME TABLE GRAPHS
• scientific article; zbMATH DE number 6770058 (Why is no real title available?)
• Wiener index and vulnerability parameters of graphs
• An efficient algorithm to compute the toughness in graphs with bounded treewidth
• The complexity of the decision problem of toughness in the class of (2t + 1)-regular graphs
• Harary index, binding number and toughness of graphs
• Strengthening some complexity results on toughness of graphs
• Recognizing tough graphs is NP-hard

This page was built for publication: On the complexity of recognizing tough graphs

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