ГАМИЛЬТОНОВОСТЬ ЛОКАЛЬНО СВЯЗНЫХ ГРАФОВ: СЛОЖНОСТНЫЕ АСПЕКТЫ
Анатацыя
В работе рассматривается вопрос о сложности задачи распознавания гамильтоновости графов с предписанной локальной структурой: локально связных графов с ограничениями на степени вершин, 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.
##reviewer.review.form##
Праглядаў: 691
Паслаць артыкул па эл. пошце 