Собственные значения, трассируемость и совершенное паросочетание графа
https://doi.org/10.29235/1561-2430-2021-57-3-274-285
Аннотация
Хорошо известно, что задача распознавания существования в графе совершенного паросочетания, как и задачи распознавания его гамильтоновости и трассируемости, является NP-полной. Совсем недавно были получены нижние оценки на размер и спектральный радиус графа, гарантирующие существование в нем совершенного паросочетания. Мы улучшаем эти оценки, во-первых, благодаря использованию имеющихся оценок на размер графа для существования в нем гамильтоновой цепи, во-вторых, благодаря нахождению новых нижних оценок на спектральный радиус графа, являющихся достаточными для наличия свойства трассируемости. Также приводится алгоритм распознавания существования в графе совершенного паросочетания, использующий понятие (κ,τ)-регулярного множества, который становится полиномиальным в классе графов с фиксированным цикломатическим числом.
Ключевые слова
гамильтоновость,
трассируемость,
совершенное паросочетание,
матрица смежности,
фактор-матрица смежности,
(κ,
τ)-регулярное множество,
спектр,
главный спектр,
спектральный радиус графа
При поддержке: Работа профинансирована Институтом математики НАН Беларуси в рамках Государственной программы фундаментальных исследований «Конвергенция» и Белорусским республиканским фондом фундаментальных исследований (проект № Ф20УКА–005).
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, г. Минск
Список литературы
1. Cvetković, D. An Introduction to the Theory of Graph Spectra / D. Cvetković, P. Rowlinson, S. Simić. – Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511801518
2. Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. – М.: Физматлит, 2010. – 560 с
3. Sciriha, I. Necessary and sufficient conditions for a Hamiltonian graphs / I. Sciriha, D. M. Cardoso // J. Combin. Math. Comb. Comput. – 2012. – Vol. 80. – P. 127–150.
4. Suil, O. Spectral radius and matchings in graphs / O. Suil // Linear Algebra Appl. – 2021. – Vol. 614. – P. 316–324. https://doi.org/10.1016/j.laa.2020.06.004
5. Ning, B. Spectral radius and Hamiltonian properties of graphs / B. Ning, J. Ge // Linear and Multilinear Algebra. – 2015. – Vol. 63, № 8. – P. 1520–1530. https://doi.org/10.1080/03081087.2014.947984
6. Yuan Hong. A sharp upper bound of the spectral radius of graphs / Yuan Hong, Jin-Long Shu, Kunfu Fang // J. Comb. Theory. Ser. B. – 2001. – Vol. 81, № 2. – P. 177–183. https://doi.org/10.1006/jctb.2000.1997
7. Bondy, J. A. Graph Theory / J. A. Bondy, U. S. R. Murty. – New York: Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5
8. Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990. – 384 с.
9. Brouwer, A. E. Spectra of Graphs / A. E. Brouwer, W. H. Haemers. – Springer Universitext, 2012.
10. Прасолов, В. В. Многочлены / В. В. Прасолов. – М.: МЦНМО, 2001. – 336 c.
11. 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
12. Бенедиктович, В. И. Главные собственные значения графа и его гамильтоновость / В. И. Бенедиктович // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2020. – Т. 56, № 4. – С. 398–407. https://doi.org/10.29235/1561-2430-2020-56-4-398-407
Рецензия
Просмотров: 750
Послать статью по эл. почте 