@article{Бенедиктович В. И.2020-12-31,
author = { Бенедиктович В. И.},
title = {Главные собственные значения графа и его гамильтоновость},
year = {2020},
doi = {10.29235/1561-2430-2020-56-4-398-407},
publisher = {NP «NEICON»},
abstract = {Понятие (κ,τ)-регулярного множества вершин впервые появилось в 2004 г. Оказалось, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и др., может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. В статье обобщаются известные свойства (κ,κ)-регулярных множеств графа на произвольные (κ,τ)-регулярные множества графов с акцентом на связь их с классическими комбинаторными структурами. Также приводится алгоритм распознавания гамильтоновости графа, который становится полиномиальным в некоторых классах графов, например в классе графов с фиксированным цикломатическим числом.},
URL = {https://www.academjournals.by/publication/12846},
eprint = {https://www.academjournals.by/files/12812},
journal = {Известия Национальной академии наук Беларуси. Серия физико-математических наук},
}