Главные собственные значения графа и его гамильтоновость
https://doi.org/10.29235/1561-2430-2020-56-4-398-407
Аннотация
Понятие (κ,τ)-регулярного множества вершин впервые появилось в 2004 г. Оказалось, что существование многих классических комбинаторных структур в графе, таких как совершенные паросочетания, гамильтоновы циклы, эффективные доминирующие множества и др., может быть охарактеризовано с помощью (κ,τ)-регулярных множеств, определение которых эквивалентно нахождению этих классических комбинаторных структур. В свою очередь определение (κ,τ)-регулярных множеств тесно связано со свойствами главного спектра графа. В статье обобщаются известные свойства (κ,κ)-регулярных множеств графа на произвольные (κ,τ)-регулярные множества графов с акцентом на связь их с классическими комбинаторными структурами. Также приводится алгоритм распознавания гамильтоновости графа, который становится полиномиальным в некоторых классах графов, например в классе графов с фиксированным цикломатическим числом.
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, г. Минск
Список литературы
1. Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. – Физматлит, 2010. – 560 с.
2. Cvetković, D. A table of connected graphs on six vertices / D. Cvetković, M. Petrić // Discrete Math. – 1984. – Vol. 50. – P. 37–49. https://doi.org/10.1016/0012-365x(84)90033-5
3. Sciriha, I. Necessary and sufficient conditions for a Hamiltonian graphs / I. Sciriha, D. M. Cardoso // J. Combin. Math. Combin. Comput. – 2012. – Vol. 80. – P. 127–150.
4. Cardoso, D. M. An overview of (κ,τ)-regular sets and their applications / D. M. Cardoso //Discrete Appl. Math. – 2019. – Vol. 269. – P. 2–10. https://doi.org/10.1016/j.dam.2018.12.020
5. Cardoso, D. M. Main eigenvalues and (κ,τ)-regular sets / D. M. Cardoso, I. Sciriha, C. Zerafa // Linear Algebra Appl. – 2010. – Vol. 432, № 9. – P. 2399–2408. https://doi.org/10.1016/j.laa.2009.07.039
6. Cvetković, D. Spectral Generalizations of Line Graphs / D. Cvetković, P. Rowlinson, S. Simić. – Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752
Рецензия
Просмотров: 827
Послать статью по эл. почте 