On the complexity of recognizing tough graphs

DOI10.1016/0012-365X(92)00047-UzbMath0802.68065MaRDI QIDQ1313820

Douglas Bauer, Aurora Morgana, Edward F. Schmeichel

Publication date: 10 March 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Hamiltonian graphNP-hardtough graph

Mathematics Subject Classification ID

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

Related Items

Polynomial algorithms that prove an NP-hard hypothesis implies an NP-hard conclusion, 1-tough cocomparability graphs are hamiltonian, The complexity of recognizing tough cubic graphs, Stability theorems for graph vulnerability parameters, Properties of minimally \(t\)-tough graphs, Wiener index and vulnerability parameters of graphs, Forbidden Induced Subgraphs for Toughness, Toughness in graphs -- a survey, Independence free graphs and vertex connectivity augmentation, Various results on the toughness of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Long cycles in graphs with large degree sums
• Recognizing tough graphs is NP-hard
• Tough graphs and Hamiltonian circuits.
• Toughness and the existence ofk-factors
• Long Cycles in Digraphs
• Some Theorems on Abstract Graphs