Recognizing tough graphs is NP-hard
type: Item
instance of: scholarly article
title: Recognizing tough graphs is NP-hard
zbMATH Open document ID: 0706.68052
DOI: 10.1016/0166-218X(90)90001-S
published in: Discrete Applied Mathematics
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 4160130
zbMATH Keywords: tough graphs
Wikidata QID: Q61248964
author: D. Bauer
author: S. Louis Hakimi
author: E. Schmeichel
MaRDI profile type: Publication
cites work: Long cycles in graphs with large degree sums
cites work: Q5422499
cites work: Tough graphs and Hamiltonian circuits.
cites work: Q3689218
cites work: Toughness and the existence ofk-factors
cites work: Q4198056
cites work: On Maximal Circuits in Finite Graphs
cites work: Long Cycles in Digraphs
full work available at URL: 0166-218x(90)90001-s
OpenAlex ID: W1981583245
DBLP publication ID: journals/dam/BauerHS90
Recommended article: On the complexity of recognizing tough graphs
Recommended article: Q5502385
Recommended article: The complexity of recognizing minimally tough graphs
Recommended article: NP-hardness of the recognition of coordinated graphs
Recommended article: Recognizing graphs with fixed interval number is NP-complete
Recommended article: The complexity of recognizing tough cubic graphs
Recommended article: Clique Graph Recognition Is NP-Complete
Recommended article: Unit disk graph recognition is NP-hard
Recommended article: Point visibility graph recognition is NP-hard
Recommended article: Discontinuities in the complexities of some graph recognition problems
description: scientific article; zbMATH DE number 4160130