On the complexity of recognizing tough graphs
type: Item
instance of: scholarly article
title: On the complexity of recognizing tough graphs
zbMATH Open document ID: 0802.68065
DOI: 10.1016/0012-365X(92)00047-U
author: D. Bauer
author: Aurora Morgana
author: E. Schmeichel
published in: Discrete Mathematics
publication date: 1994-03-10T00:00:00Z
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\).
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 500603
zbMATH Keywords: tough graph
zbMATH Keywords: NP-hard
zbMATH Keywords: Hamiltonian graph
reviewed by: Giora Slutzki
MaRDI profile type: Publication
cites work: Recognizing tough graphs is NP-hard
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: Some Theorems on Abstract Graphs
cites work: Toughness and the existence ofk-factors
cites work: Q4198056
cites work: Long Cycles in Digraphs
description: scientific article; zbMATH DE number 500603