The complexity of the decision problem of toughness in the class of (2t + 1)-regular graphs
https://doi.org/10.29235/1561-2430-2025-61-4-299-306
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.
About the Author
V. I. Benediktovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher
11, Surganov Str., 220072, Minsk
References
1. Bauer D., Hakimi S. L., Schmeichel E. Recognizing tough graphs is NP-hard. Discrete Applied Mathematics, 1990, vol. 28, no. 3, pp. 191–195. https://doi.org/10.1016/0166-218x(90)90001-s
2. Bauer D., Morgana A., Schmeichel E. On the complexity of recognizing tough graphs. Discrete Mathematics, 1994, vol. 124, no. 1–3, pp. 13–17. https://doi.org/10.1016/0012-365x(92)00047-u
3. Kratsch D., Lehel J., Müller H. Toughness, hamiltonicity and split graphs Discrete Mathematics, 1996, vol. 150, no. 1–3, pp. 231–245. https://doi.org/10.1016/0012-365x(95)00190-8
4. Bauer D., Heuvel J. van den, Morgana A., Schmeichel E. The complexity of recognizing tough cubic graphs. Discrete Applied Mathematics, 1997, vol. 79, no. 1–3, pp. 35–44. https://doi.org/10.1016/s0166-218x(97)00030-9
5. Bauer D., Heuvel J. van den, Morgana A., Schmeichel E. The complexity of toughness in regular graphs. Congressus Numerantium, 1998, vol. 130, pp. 47–61.
6. Tait P. G. On the colouring of maps. Proceedings of the Royal Society of Edinburgh, 1880, vol. 10, no. 4, pp. 501–503. https://doi.org/10.1017/S0370164600044229
7. Isaacs R. Infinite families of nontrivial trivalent graphs which are not Tait colorable. The American Mathematical Monthly, 1975, vol. 82, no. 3, pp. 221–239. https://doi.org/10.1080/00029890.1975.11993805
Review
Views:
23
Email this article 