TY  - JOUR
T1  - Главные собственные значения графа и его гамильтоновость
JF  - Известия Национальной академии наук Беларуси. Серия физико-математических наук
DO  - 10.29235/1561-2430-2020-56-4-398-407
AU  - Бенедиктович В. И., 
Y1  - 2020-12-31
UR  - https://www.academjournals.by/publication/12846
N2  - Понятие (κ,τ)-регулярного множества вершин впервые появилось в 2004 г. Оказалось, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и др., может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. В статье обобщаются известные свойства (κ,κ)-регулярных множеств графа на произвольные (κ,τ)-регулярные множества графов с акцентом на связь их с классическими комбинаторными структурами. Также приводится алгоритм распознавания гамильтоновости графа, который становится полиномиальным в некоторых классах графов, например в классе графов с фиксированным цикломатическим числом.