%0 article
%A Бенедиктович В. И., 
%T Главные собственные значения графа и его гамильтоновость
%D 2020
%R 10.29235/1561-2430-2020-56-4-398-407
%J Известия Национальной академии наук Беларуси. Серия физико-математических наук
%X Понятие (κ,τ)-регулярного множества вершин впервые появилось в 2004 г. Оказалось, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и др., может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. В статье обобщаются известные свойства (κ,κ)-регулярных множеств графа на произвольные (κ,τ)-регулярные множества графов с акцентом на связь их с классическими комбинаторными структурами. Также приводится алгоритм распознавания гамильтоновости графа, который становится полиномиальным в некоторых классах графов, например в классе графов с фиксированным цикломатическим числом.
%U https://www.academjournals.by/publication/12846