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

Бенедиктович В. И.

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

Бенедиктович В. И.

2019

https://doi.org/10.29235/1561-2430-2019-55-2-169-175

Рассматривается графовый параметр – окружность графа – и его взаимосвязь с алгебраическими параметрами графа – собственными значениями матрицы смежности и беззнаковой матрицы Лапласа графа. Ранее нами были получены нижние оценки спектрального радиуса произвольного графа и двудольного сбалансированного графа для существования в нем гамильтонового цикла. Недавно была исследована задача существования цикла длины n – 1 в графе в зависимости от значений его вышеназванных спектральных радиусов. В настоящей работе изучается задача существования цикла длины n – 2 в графе в зависимости от нижних оценок значений его спектрального радиуса и спектрального радиуса его беззнакового лапласиана и получены спектральные условия существования максимального цикла в графе (двухсвязном графе).

Бенедиктович В. И. Спектральные условия существования максимального цикла в графе. Известия Национальной академии наук Беларуси. Серия физико-математических наук. 2019;55(2):169-175. https://doi.org/10.29235/1561-2430-2019-55-2-169-175

Цитирование

Список литературы

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

Источник

Информация

Автор

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

Страницы

169-175

Год издания

2019

Ключевые слова

Коллекции

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