The complexity of the decision problem of toughness in the class of (2t + 1)-regular graphs
Abstract
It is known that the decision problem of t-TOUGHNESS of a graph is coNP-complete in general. Moreover, in many subclasses of graphs, the decision problem of t-TOUGHNESS remains NP-hard, in particular, in the class of r-regular graphs, where r ≥ 3t for any integer number t ≥ 1. The complexity of the decision problem of t-TOUGHNESS for r-regular graphs remains open when 2t ≤ r < 3t, and when r = 2t + 1 the complexity of the decision problem is particularly intriguing. In the latter case it has been conjectured, that it remains NP-hard. In this paper, we establish the validity of this conjecture.
Fields of Study & Subjects
Finite Group Theory Research
graph theory and CDMA systems
Advanced Graph Theory Research
Publication details
- Journal / source
- Proceedings of the National Academy of Sciences of Belarus Physics and Mathematics Series
- Publisher
- Publishing House Belorusskaya Nauka
- Volume
- 61
- Issue
- 4
- Pages
- 299–306
- Publication date
- 6 January 2026