@article{Иржавский П. А.2016-05-19,
author = { Иржавский П. А.},
title = {ГАМИЛЬТОНОВОСТЬ ЛОКАЛЬНО СВЯЗНЫХ ГРАФОВ: СЛОЖНОСТНЫЕ АСПЕКТЫ},
year = {2014},
publisher = {NP «NEICON»},
abstract = {В работе рассматривается вопрос о сложности задачи распознавания гамильтоновости графов с предписанной локальной структурой: локально связных графов с ограничениями на степени вершин, N2-локально связных К1 3-свободных графов и локально связных почти К1 3-свободных графов. Установлена NP-полнота задачи в каждом из рассматриваемых классов графов, тем самым, в частности, опровергнута гипотеза, выдвинутая в 2011 г., о полиномиальной разрешимости задачи о гамильтоновом цикле в классе локально связных графов со степенями вершин, не превосходящими 6. Также показано, что некоторые полученные ранее достаточные условия гамильтоновости не могут быть естественным образом ослаблены без потери свойства полиномиальной разрешимости задачи о гамильтоновом цикле.},
URL = {https://www.academjournals.by/publication/13157},
eprint = {https://www.academjournals.by/files/13123},
journal = {Известия Национальной академии наук Беларуси. Серия физико-математических наук},
}