TY  - JOUR
T1  - ГАМИЛЬТОНОВОСТЬ ЛОКАЛЬНО СВЯЗНЫХ ГРАФОВ: СЛОЖНОСТНЫЕ АСПЕКТЫ
JF  - Известия Национальной академии наук Беларуси. Серия физико-математических наук
AU  - Иржавский П. А., 
Y1  - 2016-05-19
UR  - https://www.academjournals.by/publication/13157
N2  - В работе рассматривается вопрос о сложности задачи распознавания гамильтоновости графов с предписанной локальной структурой: локально связных графов с ограничениями на степени вершин, N2-локально связных К1 3-свободных графов и локально связных почти К1 3-свободных графов. Установлена NP-полнота задачи в каждом из рассматриваемых классов графов, тем самым, в частности, опровергнута гипотеза, выдвинутая в 2011 г., о полиномиальной разрешимости задачи о гамильтоновом цикле в классе локально связных графов со степенями вершин, не превосходящими 6. Также показано, что некоторые полученные ранее достаточные условия гамильтоновости не могут быть естественным образом ослаблены без потери свойства полиномиальной разрешимости задачи о гамильтоновом цикле.