%0 article
%A Бенедиктович В. И., 
%T Спектральные достаточные условия существования максимальной цепи в графе и его трассируемость
%D 2022
%R 10.29235/1561-2430-2022-58-2-169-178
%J Известия Национальной академии наук Беларуси. Серия физико-математических наук
%X Известно, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и другие, может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь, определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. Нами используются полученные ранее обобщенные свойства (κ,τ)-регулярных множеств графов для разработки алгоритма распознавания трассируемости графа. Также получены новые достаточные условия существования максимальной простой цепи в графе в терминах спектрального радиуса матрицы смежности и беззнаковой матрицы Лапласа графа.
%U https://www.academjournals.by/publication/12728