Add to ORKGWe show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this result to show that for any integer t # 1, it is NP-hard to determine if a 3 t-regular graph is t-tough. We conclude with some remarks concerning the complexity of recognizing certain subclasses of tough graphs. Keywords : toughness, cubic graphs, NP-completeness AMS Subject Classifications (1991) : 68R10, 05C38 # Supported in part by NATO Collaborative Research Grant CRG 921251. + Supported by a grant from the Natural Sciences and Engineering Council of Canada. # Current address : Centre for Discrete and Applicable Mathematics, Department of Mathematics, London School of Economics, Houghton Street, London WC2A 2AE, England, U.K. Supported in p...
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A...
AbstractGiven a graph G and an integer r, does there exist a regular subgraph of G with degree r? In...
AbstractIt was proved by [M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebrai...
AbstractWe show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this resu...
AbstractWe consider the relationship between the minimum degree δ of a graph and the complexity of r...
In this survey we have attempted to bring together most of the results and papers that deal with tou...
Let G be a graph, and let t 0 be a real number. Then G is t-tough if t!(G − S) jSj for all S V (G) w...
In this short note we argue that the toughness of split graphs can be computed in polynomial time. T...
AbstractWe show that, if NP≠ZPP, for any ε>0, the toughness of a graph with n vertices is not approx...
Let $t$ be a positive real number. A graph is called $t$-tough if the removalof any vertex set $S$ t...
The concept of toughness was introduced by Chvátal [34] more than forty years ago. Toughness resembl...
In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, ther...
this paper only finite, undirected and simple graphs are considered. In 1973 Chv'atal [4] intro...
AbstractIn this paper, we prove that there exist triangle-free graphs with arbitrarily large toughne...
A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interv...
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A...
AbstractGiven a graph G and an integer r, does there exist a regular subgraph of G with degree r? In...
AbstractIt was proved by [M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebrai...
AbstractWe show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this resu...
AbstractWe consider the relationship between the minimum degree δ of a graph and the complexity of r...
In this survey we have attempted to bring together most of the results and papers that deal with tou...
Let G be a graph, and let t 0 be a real number. Then G is t-tough if t!(G − S) jSj for all S V (G) w...
In this short note we argue that the toughness of split graphs can be computed in polynomial time. T...
AbstractWe show that, if NP≠ZPP, for any ε>0, the toughness of a graph with n vertices is not approx...
Let $t$ be a positive real number. A graph is called $t$-tough if the removalof any vertex set $S$ t...
The concept of toughness was introduced by Chvátal [34] more than forty years ago. Toughness resembl...
In this paper, we prove that there exist triangle-free graphs with arbitrarily large toughness, ther...
this paper only finite, undirected and simple graphs are considered. In 1973 Chv'atal [4] intro...
AbstractIn this paper, we prove that there exist triangle-free graphs with arbitrarily large toughne...
A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interv...
The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A...
AbstractGiven a graph G and an integer r, does there exist a regular subgraph of G with degree r? In...
AbstractIt was proved by [M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebrai...