Спектральные достаточные условия существования максимальной цепи в графе и его трассируемость

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

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. Бенедиктович, В. И. Собственные значения, трассируемость и совершенное паросочетание графа / В. И. Бенедиктович // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2021. – Т. 57, № 3. – С. 274–285. https://doi.org/10.29235/15612430-2021-57-3-274-285

5. Копылов, Г. Н. О максимальных путях и циклах в графе / Г. Н. Копылов // Докл. Акад. наук СССР. – 1977. – Т. 234, № 1. – С. 19–21.

6. Hong, Y. A sharp upper bound of the spectral radius of graphs / Y. Hong, J. Shu, K. 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. 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

9. Бенедиктович, В. И. Главные собственные значения графа и его гамильтоновость / В. И. Бенедиктович // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2020. – Т. 56, № 4. – С. 398–407. https://doi.org/10.29235/1561-24302020-56-4-398-407

10. Cvetković, D. Spectral generalizations of line graphs / D. Cvetković, P. Rowlinson, S. Simić // London Mathematical Society Lecture Note Series. – Cambridge University Press, 2004. – Vol. 314. https://doi.org/10.1017/cbo9780511751752