vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"vestifm-134Research ArticleМАТЕМАТИКАMATHEMATICSГАМИЛЬТОНОВОСТЬ ЛОКАЛЬНО СВЯЗНЫХ ГРАФОВ: СЛОЖНОСТНЫЕ АСПЕКТЫHAMLTONICITY OF LOCALLY CONNECTED GRAPHS: COMPLEXITY RESULTSИржавскийП. А.IrzhavskiP. A.Белорусский государственный университет, МинскBelarusian State University, Minsk201419052016043743Copyright © Иржавский П.А., 20162016Иржавский П.А.Irzhavski P.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/134

В работе рассматривается вопрос о сложности задачи распознавания гамильтоновости графов с предписанной локальной структурой: локально связных графов с ограничениями на степени вершин, N2-локально связных К1 3-свободных графов и локально связных почти К1 3-свободных графов. Установлена NP-полнота задачи в каждом из рассматриваемых классов графов, тем самым, в частности, опровергнута гипотеза, выдвинутая в 2011 г., о полиномиальной разрешимости задачи о гамильтоновом цикле в классе локально связных графов со степенями вершин, не превосходящими 6. Также показано, что некоторые полученные ранее достаточные условия гамильтоновости не могут быть естественным образом ослаблены без потери свойства полиномиальной разрешимости задачи о гамильтоновом цикле.

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.

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

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