Сложность распознавания жесткости в классе (2t + 1)-регулярных графов
https://doi.org/10.29235/1561-2430-2025-61-4-299-306
Аннотация
Известно, что в общем случае проблема распознавания t-ЖЕСТКОСТИ графа является coNPполной. Кроме того, для многих подклассов графов задача распознавания t-ЖЕСТКОСТИ остается NP-трудной, в частности, в классе r-регулярных графов, где r ≥ 3t для любого целого числа t ≥ 1. Сложность распознавания t-ЖЕСТКОСТИ r-регулярных графов остается открытой, когда 2t ≤ r < 3t, а когда r = 2t + 1 сложность распознавания является особенно интригующей. В последнем случае была выдвинута гипотеза, что она остается NP-трудной. В данной статье мы устанавливаем справедливость этой гипотезы.
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, Минск
Список литературы
1. Bauer, 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-s
2. Bauer, 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-u
3. Kratsch, 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-8
4. The 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-9
5. The complexity of toughness in regular graphs / D. Bauer, J van den Heuvel, A. Morgana, E. Schmeichel // Congressus Numerantium. – 1998. – Vol. 130. – P. 47–61.
6. 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/S0370164600044229
7. Isaacs, 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.11993805
Рецензия
Просмотров:
18
Послать статью по эл. почте 