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