THE COMPLEXITY OF RECOGNIZING TOUGH CUBIC GRAPHS

Authors
BAUER D VANDENHEUVEL J MORGANA A SCHMEICHEL E
Citation
D. Bauer et al., THE COMPLEXITY OF RECOGNIZING TOUGH CUBIC GRAPHS, Discrete applied mathematics, 79(1-3), 1997, pp. 35-44
Citations number
25
Categorie Soggetti
Mathematics,Mathematics
Journal title
Discrete applied mathematics → ACNP
Volume
79
Issue
1-3
Year of publication
1997
Pages
35 - 44
Database
ISI
SICI code
Abstract
We 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 greater than o r equal to 1, it is NP-hard to determine if a 3 t-regular graph is t-t ough. We conclude with some remarks concerning the complexity of recog nizing certain subclasses of tough graphs.