HAMLTONICITY OF LOCALLY CONNECTED GRAPHS: COMPLEXITY RESULTS
Abstract
In this article we consider the complexity of recognizing Hamiltonian graphs with a prescribed local structure: locally connected graphs with a bounded vertex degree, N2-locally connected K1 3-free graphs and locally connected almost K1, 3-free graphs. We establish the NP-completeness of the problem for each class of graphs under consideration. In particular, the conjecture stated in 2011 on polynomial solvability of the Hamiltonian cycle problem for locally connected graphs of maximum degree at most 6 was disproved. Also, for several known sufficient conditions of Hamiltonicity, it is shown that these conditions cannot be naturally weakened without loss of the polynomial solvability of the Hamiltonian cycle problem.
References
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.
Review
Views: 688
Email this article 