vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2025-61-4-299-306vestifm-863Research ArticleМАТЕМАТИКАMATHEMATICSСложность распознавания жесткости в классе (2t + 1)-регулярных графовThe complexity of the decision problem of toughness in the class of (2t + 1)-regular graphsБенедиктовичВ. И.BenediktovichV. I.

Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник

ул. Сурганова, 11, 220072, Минск 

Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher

11, Surganov Str., 220072, Minsk

vbened@im.bas-net.byИнститут математики Национальной академии наук БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus202506012026614299306Copyright © Бенедиктович В.И., 20262026Бенедиктович В.И.Benediktovich V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/863

Известно, что в общем случае проблема распознавания t-ЖЕСТКОСТИ графа является coNPполной. Кроме того, для многих подклассов графов задача распознавания t-ЖЕСТКОСТИ остается NP-трудной, в частности, в классе r-регулярных графов, где r ≥ 3t для любого целого числа t ≥ 1. Сложность распознавания t-ЖЕСТКОСТИ r-регулярных графов остается открытой, когда 2t ≤ r < 3t, а когда r = 2t + 1 сложность распознавания является особенно интригующей. В последнем случае была выдвинута гипотеза, что она остается NP-трудной. В данной статье мы устанавливаем справедливость этой гипотезы.

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.

вершинный разрез графаt-ЖЕСТКОСТЬ графаcoNP-полнота проблемы распознаванияvertex cut of a grapht-toughness of a graphcoNP-completeness of the decision problemReferencesBauer, D. Recognizing tough graphs is NP-hard / D. Bauer, S. L. Hakimi, E. Schmeichel // Discrete Applied Mathematics. – 1990. – Vol. 28, № 3. – P. 191–195. https://doi.org/10.1016/0166-218x(90)90001-sBauer 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-sBauer, D. On the complexity of recognizing tough graphs / D. Bauer, A. Morgana, E. Schmeichel // Discrete Mathematics. – 1994. – Vol. 124, № 1–3. – P. 13–17. https://doi.org/10.1016/0012-365x(92)00047-uBauer 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-uKratsch, D. Toughness, hamiltonicity and split graphs / D. Kratsch, J. Lehel, H. Müller // Discrete Mathematics. – 1996. – Vol. 150, № 1–3. – P. 231–245. https://doi.org/10.1016/0012-365x(95)00190-8Kratsch 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-8The complexity of recognizing tough cubic graphs / D. Bauer, J. van den Heuvel, A. Morgana, E. Schmeichel // Discrete Applied Mathematics. – 1997. – Vol. 79, № 1–3. – P. 35–44. https://doi.org/10.1016/s0166-218x(97)00030-9Bauer 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-9The complexity of toughness in regular graphs / D. Bauer, J van den Heuvel, A. Morgana, E. Schmeichel // Congressus Numerantium. – 1998. – Vol. 130. – P. 47–61.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.Tait, P. G. On the colouring of maps / P. G. Tait // Proceedings of the Royal Society of Edinburgh. – 1880. – Vol. 10, № 4. – P. 501–503. https://doi.org/10.1017/S0370164600044229Tait 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/S0370164600044229Isaacs, R. Infinite families of nontrivial trivalent graphs which are not Tait colorable / R. Isaacs // The American Mathematical Monthly. – 1975. – Vol. 82, № 3. – P. 221–239. https://doi.org/10.1080/00029890.1975.11993805Isaacs 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

The authors declare that there are no conflicts of interest present.