Recommendations
- On the complexity of recognizing tough graphs
- Recognizing tenacious graphs is NP-hard.
- The complexity of recognizing minimally tough graphs
- NP-hardness of the recognition of coordinated graphs
- Recognizing graphs with fixed interval number is NP-complete
- The complexity of recognizing tough cubic graphs
- Clique Graph Recognition Is NP-Complete
- Unit disk graph recognition is NP-hard
- Point visibility graph recognition is NP-hard
- Discontinuities in the complexities of some graph recognition problems
Cites work
- scientific article; zbMATH DE number 3912424 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Graph theory
- Long Cycles in Digraphs
- Long cycles in graphs with large degree sums
- On Maximal Circuits in Finite Graphs
- Tough graphs and Hamiltonian circuits.
- Toughness and the existence ofk-factors
Cited in
(49)- An efficient algorithm to compute the toughness in graphs with bounded treewidth
- A note on dominating cycles in 2-connected graphs
- Bipartite toughness and \(k\)-factors in bipartite graphs
- Fixed edge-length graph drawing is NP-hard
- On the toughness index of planar graphs
- Computing the Scattering Number of Graphs
- Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
- The scattering number of strictly chordal graphs: linear time determination
- Link vulnerability in networks
- Node and link vulnerability in complete multipartite networks
- scientific article; zbMATH DE number 2230266 (Why is no real title available?)
- scientific article; zbMATH DE number 7310279 (Why is no real title available?)
- Better approximations of non-Hamiltonian graphs
- Measuring the vulnerability for classes of intersection graphs
- Best monotone degree conditions for graph properties: a survey
- A large set of non-Hamiltonian graphs
- On one extension of Dirac's theorem on Hamiltonicity
- 1-tough cocomparability graphs are hamiltonian
- Toughness, binding number and restricted matching extension in a graph
- Toughness in graphs -- a survey
- Computing the binding number of a graph
- Approximation and kernelization for chordal vertex deletion
- Toughness, hamiltonicity and split graphs
- Characterization of 1-tough graphs using factors
- The vertex attack tolerance of complex networks
- An upper bound on the shortness exponent of 1-tough, maximal planar graphs
- Recognition of split-graphic sequences
- The complexity of recognizing minimally tough graphs
- String graphs. II: Recognizing string graphs is NP-hard
- Maximum and minimum toughness of graphs of small genus
- Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion
- Toughness and Delaunay triangulations
- Toughness and binding number
- A polynomial algorithm for weighted scattering number in interval graphs
- A brief account on the development and future research directions of connectivity properties of interconnection networks
- Recognizing tenacious graphs is NP-hard.
- A note on the approximability of the toughness of graphs
- A note on the link residual closeness of graphs under join operation
- Chvátal's \(t_{0}\)-tough conjecture
- Graph invariants and large cycles: a survey
- Computational complexity of network vulnerability analysis
- On the complexity of recognizing tough graphs
- Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
- Toughness of the corona of two graphs
- scientific article; zbMATH DE number 2230273 (Why is no real title available?)
- On toughness and Hamiltonicity of \(2K_{2}\)-free graphs
- Approximation of coNP sets by NP-complete sets
- The toughness of split graphs
- The complexity of recognizing tough cubic graphs
This page was built for publication: Recognizing tough graphs is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q918697)
