Recognizing tough graphs is NP-hard
From MaRDI portal
Publication:918697
DOI10.1016/0166-218X(90)90001-SzbMath0706.68052OpenAlexW1981583245WikidataQ61248964 ScholiaQ61248964MaRDI QIDQ918697
Edward F. Schmeichel, Douglas Bauer, S. Louis Hakimi
Publication date: 1990
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(90)90001-s
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Eulerian and Hamiltonian graphs (05C45)
Related Items
Computing the Scattering Number of Graphs ⋮ Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion ⋮ Toughness of the corona of two graphs ⋮ On one extension of Dirac's theorem on Hamiltonicity ⋮ The scattering number of strictly chordal graphs: linear time determination ⋮ On the toughness index of planar graphs ⋮ Maximum and minimum toughness of graphs of small genus ⋮ 1-tough cocomparability graphs are hamiltonian ⋮ Measuring the vulnerability for classes of intersection graphs ⋮ The complexity of recognizing tough cubic graphs ⋮ The complexity of recognizing minimally tough graphs ⋮ Toughness, binding number and restricted matching extension in a graph ⋮ Toughness, hamiltonicity and split graphs ⋮ A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks ⋮ The vertex attack tolerance of complex networks ⋮ Better approximations of non-Hamiltonian graphs ⋮ A note on dominating cycles in 2-connected graphs ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Characterization of 1-tough graphs using factors ⋮ Approximation of coNP sets by NP-complete sets ⋮ A polynomial algorithm for weighted scattering number in interval graphs ⋮ Computational complexity of network vulnerability analysis ⋮ Toughness and binding number ⋮ A Note on the Link Residual Closeness of Graphs Under Join Operation ⋮ Best monotone degree conditions for graph properties: a survey ⋮ Link Vulnerability in Networks ⋮ Recognition of split-graphic sequences ⋮ On Toughness and Hamiltonicity of 2K2‐Free Graphs ⋮ Graph invariants and large cycles: a survey ⋮ Toughness in graphs -- a survey ⋮ A large set of non-Hamiltonian graphs ⋮ Bipartite toughness and \(k\)-factors in bipartite graphs ⋮ Computing the binding number of a graph ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A note on the approximability of the toughness of graphs ⋮ Unnamed Item ⋮ The toughness of split graphs ⋮ Chvátal’s t 0-Tough Conjecture ⋮ Toughness and Delaunay triangulations ⋮ On the complexity of recognizing tough graphs ⋮ An upper bound on the shortness exponent of 1-tough, maximal planar graphs ⋮ Linear‐Time Algorithms for Scattering Number and Hamilton‐Connectivity of Interval Graphs ⋮ Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness
Cites Work
