Спектральные условия существования максимального цикла в графе
https://doi.org/10.29235/1561-2430-2019-55-2-169-175
Аннотация
Рассматривается графовый параметр – окружность графа – и его взаимосвязь с алгебраическими параметрами графа – собственными значениями матрицы смежности и беззнаковой матрицы Лапласа графа. Ранее нами были получены нижние оценки спектрального радиуса произвольного графа и двудольного сбалансированного графа для существования в нем гамильтонового цикла. Недавно была исследована задача существования цикла длины n – 1 в графе в зависимости от значений его вышеназванных спектральных радиусов. В настоящей работе изучается задача существования цикла длины n – 2 в графе в зависимости от нижних оценок значений его спектрального радиуса и спектрального радиуса его беззнакового лапласиана и получены спектральные условия существования максимального цикла в графе (двухсвязном графе).
Ключевые слова
окружность графа,
минимальная и максимальная степени графа,
матрица смежности,
беззнаковая матрица Лапласа графа,
спектральный радиус
При поддержке: Работа выполнена при финансовой поддержке Института математики Национальной академии наук Беларуси в рамках Государственной программы фундаментальных исследований «Конвер-генция-2020» и Белорусского республиканского фонда фундаментальных исследований в рамках проекта № Ф18РА–014.
Об авторе
В. И. Бенедиктович
Институт математики Национальной академии Беларуси
Беларусь
Беларусь
Бенедиктович Владимир Иванович – кандидат физико-математических наук, ведущий научный сотрудник
ул. Сурганова, 11, 220072, г. Минск, Республика Беларусь
Список литературы
1. Li, B. Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles / B. Li, B. Ning // Linear and Multilinear Algebra. – 2016. – Vol. 64, № 11. – P. 2252–2269. https://doi.org/10.1080/03081087.2016.1151854
2. Li, B. Spectral analogues of Moon–Moser’s theorem on Hamilton paths in bipartite graphs / B. Li, B. Ning // Linear Algebra and its Applications. – 2017. – Vol. 515. – P. 180–195. https://doi.org/10.1016/j.laa.2016.11.024
3. Nikiforov, V. Spectral radius and Hamiltonicity of graphs with large minimum degree / V. Nikiforov // Czechoslovak Math. J. – 2016. – Vol. 66, № 3. – P. 925–940. https://doi.org/10.1007/s10587-016-0301-y
4. 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
5. Benediktovich, V. I. Spectral condition for Hamiltonicity of a graph / V. I. Benediktovich // Linear Algebra and its Applications. – 2016. – Vol. 494. – P. 70–79. https://doi.org/10.1016/j.laa.2016.01.005
6. Бенедиктович, В. И. Спектральный радиус сбалансированного двудольного графа и его гамильтоновость / В. И. Бенедиктович // Докл. Нац. акад. наук Беларуси. – 2017. – т. 61, № 2. – С. 7–12.
7. Ge, J. Spectral radius and Hamiltonian properties of graphs, II / J. Ge, B. Ning // Linear and Multilinear Algebra. – 2019. – P. 1–18. https://doi.org/10.1080/03081087.2019.1580668
8. Bondy, J. A. Pancyclic graphs I / J. A. Bondy // J. Combinatorial Theory, Ser. B. – 1971. – Vol. 11, № 1. – P. 80–84. https://doi.org/10.1016/0095-8956(71)90016-5
9. Копылов, Г. Н. О максимальных путях и циклах в графе / Г. Н. Копылов // Докл. Акад. наук СССР. – 1977. – т. 234, № 1. – С. 19–21.
10. Hong, Y. Bounds of eigenvalues of graphs / Y. Hong // Discrete Mathematics. – 1993. – Vol. 123, № 1–3. – P. 65–74. https://doi.org/10.1016/0012-365x(93)90007-g
11. 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
12. Feng, L. On three conjectures involving the signless Laplacian spectral radius of graphs / L. Feng, G. Yu // Publications de l’Institut Mathématique. – 2009. – Vol. 85, № 99. – P. 35–38. https://doi.org/10.2298/pim0999035f
Рецензия
Просмотров: 852
Послать статью по эл. почте 