Preview

Известия Национальной академии наук Беларуси. Серия физико-математических наук

Расширенный поиск

Собственные значения, трассируемость и совершенное паросочетание графа

https://doi.org/10.29235/1561-2430-2021-57-3-274-285

Полный текст:

Аннотация

Хорошо известно, что задача распознавания существования в графе совершенного паросочетания, как и задачи распознавания его гамильтоновости и трассируемости, является NP-полной. Совсем недавно были получены нижние оценки на размер и спектральный радиус графа, гарантирующие существование в нем совершенного паросочетания. Мы улучшаем эти оценки, во-первых, благодаря использованию имеющихся оценок на размер графа для существования в нем гамильтоновой цепи, во-вторых, благодаря нахождению новых нижних оценок на спектральный радиус графа, являющихся достаточными для наличия свойства трассируемости. Также приводится алгоритм распознавания существования в графе совершенного паросочетания, использующий понятие (κ,τ)-регулярного множества, который становится полиномиальным в классе графов с фиксированным цикломатическим числом.

Об авторе

В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь

Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник

ул. Сурганова, 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


Просмотров: 191


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1561-2430 (Print)
ISSN 2524-2415 (Online)