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)

Review text

Let G be an undirected graph without loops or multiple edges. Let V(G), \(\omega\)(G), and \(\delta\)(G) denote the vertex set, independence number, and minimum vertex degree of G. Let \(t\) be any positive real number. G is said to be \(t\)-tough if \(t\omega\)(G-- X)\(\leq |\)X\(|\) for all X\( \subseteq\)V(G) with \(\omega\)(G-X)\(\geq 2\). The authors consider the relationship between the minimum degree \(\delta\)(G) and the complexity of recognizing if a graph is \(t\)-tough. Specifically, they prove the following claims. (a) If \(\delta\)(G)\(\geq \text{tn}/(t + 1)\), then G is \(t\)-tough. (b) For any \(\varepsilon > 0\), it is NP-hard to determine if G is \(t\)- tough, even for the class of graphs with \(\delta\)(G)\(\geq (t/(t - 1) - \varepsilon)n\).

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)