ГАМИЛЬТОНОВОСТЬ ЛОКАЛЬНО СВЯЗНЫХ ГРАФОВ: СЛОЖНОСТНЫЕ АСПЕКТЫ
Аннотация
В работе рассматривается вопрос о сложности задачи распознавания гамильтоновости графов с предписанной локальной структурой: локально связных графов с ограничениями на степени вершин, N2-локально связных К1 3-свободных графов и локально связных почти К1 3-свободных графов. Установлена NP-полнота задачи в каждом из рассматриваемых классов графов, тем самым, в частности, опровергнута гипотеза, выдвинутая в 2011 г., о полиномиальной разрешимости задачи о гамильтоновом цикле в классе локально связных графов со степенями вершин, не превосходящими 6. Также показано, что некоторые полученные ранее достаточные условия гамильтоновости не могут быть естественным образом ослаблены без потери свойства полиномиальной разрешимости задачи о гамильтоновом цикле.
При поддержке: Белорусский РФФИ
Список литературы
1. Karp R. M. // Proc. of a Symp. on the Complexity of Computer Computations. New York, 1972. P. 85-103.
2. Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М., 1990.
3. Hendry G. R. T. // J. Graph Theory. 1989. Vol. 13. P. 257-260.
4. Chartrand G., PippertR. // Cas. Pest. Mat. 1974. Vol. 99. P. 158-163.
5. RyjacekZ. // J. Graph Theory. 1990. Vol. 14. P. 321-331.
6. Wang J, Teng Y. // Adv. Math. 2006. Vol. 35. P 657-662 (in Chinese).
7. Ryjacek Z. // J. Graph Theory. 1994. Vol. 18. P. 469-477.
8. Garey M. R., Johnson D. S., Tarjan R. E. // SIAM J. Comput. 1976. Vol. 5. P. 704-714.
9. Gordon V S., Orlovich Yu. L., Potts C. N., Strusevich V A. // Discrete Appl. Math. 2011. Vol. 159. P. 1759-1774.
10. Picouleau C. // Theor. Comput. Sci. 1994. Vol. 131. P. 463-473.
11. Иржавский П. А., Орлович Ю. Л. // Тр. Ин-та математики НАН Беларуси. 2012. Т. 20, № 2. С. 36-50.
12. Oberly D. J., SumnerD. P. // J. Graph Theory. 1979. Vol. 3. P 351-356.
Рецензия
Просмотров: 689
Послать статью по эл. почте 