Дистанционный спектральный радиус и гамильтоновость графа
https://doi.org/10.29235/1561-2430-2023-59-1-62-70
Аннотация
В последние годы собственные значения матрицы расстояний графа привлекают все большее внимание математиков, поскольку существует тесная связь ее спектра со структурными свойствами графа. Так, совсем недавно был получен интересный результат, связывающий гамильтоновость графа с дистанционным спектральным радиусом графа, на основе которого была сформулирована более общая гипотеза о гамильтоновости графа. Мы подтверждаем выдвинутую гипотезу для k-связного графа, когда k Î{2;3}, а также устанавливаем аналогичные достаточные условия трассируемости k-связного графа, когда k Î{1; 2}.
Ключевые слова
k-связность,
гамильтоновость,
трассируемость графа,
дистанционная матрица графа,
спектр,
дистанционный спектральный радиус графа
При поддержке: Работа профинансирована Институтом математики Национальной академии наук Беларуси в рамках Государственной программы научных исследований «Конвергенция 2025».
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии наук Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, Минск
Список литературы
1. Godsil, C. Algebraic Combinatorics / C. Godsil. – New York: Routledge, 2017. – 368 p. https://doi.org/10.1201/9781315137131
2. Huiqiu Lin. Extremal problems on distance spectra of graphs / Huiqiu Lin, Yuke Zhang // Discrete Appl. Math. – 2021. – Vol. 289. – P. 139–147. https://doi.org/10.1016/j.dam.2020.09.023
3. Прасолов, В. В. Многочлены / В. В. Прасолов. – 2-е изд. – М.: МЦНМО, 2001. – 336 с.
4. Bose, S. S. On the maximal distance spectral radius of graphs without a pendent vertex / S. S. Bose, M. Nath, S. Paul // Linear Algebra and its Applications. – 2013. – Vol. 438, № 11. – P. 4260–4278. https://doi.org/10.1016/j.laa.2013.01.019
5. On sufficient spectral radius conditions for hamiltonicity of k-connected graphs / Q. Zhou [et al.] // Linear Algebra and its Applications. – 2020. – Vol. 604. – P. 129–145. https://doi.org/10.1016/j.laa.2020.06.012
6. Bondy, J. A. A method in graph theory / J. A. Bondy, V. Chvátal // Discrete Math. – 1976. – Vol. 15, № 2. – P. 111–135. https://doi.org/10.1016/0012-365x(76)90078-9
Рецензия
Просмотров: 326
Послать статью по эл. почте 