The complexity of recognizing tough cubic graphs

✍ Scribed by D. Bauer; J. van den Heuvel; A. Morgana; E. Schmeichel

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 647 KB
• Volume: 79
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(97)00030-9

✦ Synopsis

We show that it is NP-hard to determine if a cubic graph G is l-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.