PT - JOURNAL ARTICLE
AU - Бенедиктович В. И., 
TI - Спектральные достаточные условия существования максимальной цепи в графе и его трассируемость
DP - 2022-07-05
TA - Известия Национальной академии наук Беларуси. Серия физико-математических наук
4100 - 10.29235/1561-2430-2022-58-2-169-178
SO - https://www.academjournals.by/publication/12728
AB - Известно, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и другие, может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь, определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. Нами используются полученные ранее обобщенные свойства (κ,τ)-регулярных множеств графов для разработки алгоритма распознавания трассируемости графа. Также получены новые достаточные условия существования максимальной простой цепи в графе в терминах спектрального радиуса матрицы смежности и беззнаковой матрицы Лапласа графа.