vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2019-55-2-169-175vestifm-383Research ArticleМАТЕМАТИКАMATHEMATICSСпектральные условия существования максимального цикла в графеSpectral conditions of existence of the graph circumferenceБенедиктовичВ. И.BenediktovichV. I.

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

ул. Сурганова, 11, 220072, г. Минск, Республика Беларусь

Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher

11, Surganov Str., 220072, Minsk, Republic of Belarus

vbened@im.bas-net.byИнститут математики Национальной академии БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus201928062019552169175Copyright © Бенедиктович В.И., 20192019Бенедиктович В.И.Benediktovich V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/383

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

A graph parameter – a circumference of a graph – and its relationship with the algebraic parameters of a graph – eigenvalues of the adjacency matrix and the unsigned Laplace matrix of a graph – are considered in this article. Earlier we have obtained the lower estimates of the spectral radius of an arbitrary graph and a bipartitebalanced graph for existence of the Hamiltonian cycle in it. Recently the problem of existence of a cycle of length n – 1 in a graph depending on the values of its above-mentioned spectral radii has been investigated. This article studies the problem of existence of a cycle of length n – 2 in a graph depending on the lower estimates of the values of its spectral radius and the spectral radius of its unsigned Laplacian and the spectral conditions of existence of the circumference of a graph (2-connected graph) are obtained.

окружность графаминимальная и максимальная степени графаматрица смежностибеззнаковая матрица Лапласа графаспектральный радиусcircumference of graphminimum and maximum degreeadjacency matrixunsigned Laplacian of graphspectral radiusРабота выполнена при финансовой поддержке Института математики Национальной академии наук Беларуси в рамках Государственной программы фундаментальных исследований «Конвер-генция-2020» и Белорусского республиканского фонда фундаментальных исследований в рамках проекта № Ф18РА–014.The work has been financially supported by the Institute of Mathematics of the National Academy of Sciences of Belarus within the framework of the Government Research Program “Convergence-2020” and by the Belarusian Republican Foundation for Fundamental Research within the framework of the Project No. Ф18РА–014.ReferencesLi, 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.1151854Li B., Ning B. Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles. Linear and Multilinear Algebra, 2016, vol. 64, no. 11, pp. 2252–2269. https://doi.org/10.1080/03081087.2016.1151854Li, 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.024Li B., Ning B. Spectral analogues of Moon–Moser’s theorem on Hamilton paths in bipartite graphs. Linear Algebra and its Applications, 2017, vol. 515, pp. 180–195. https://doi.org/10.1016/j.laa.2016.11.024Nikiforov, 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-yNikiforov V. Spectral radius and Hamiltonicity of graphs with large minimum degree. Czechoslovak Mathematical Journal, 2016, vol. 66, no. 3, pp. 925–940. https://doi.org/10.1007/s10587-016-0301-yNing, 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.947984Ning B., Ge J. Spectral radius and Hamiltonian properties of graphs. Linear and Multilinear Algebra, 2015, vol. 63, no. 8, pp. 1520–1530. https://doi.org/10.1080/03081087.2014.947984Benediktovich, 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.005Benediktovich V. I. Spectral condition for Hamiltonicity of a graph. Linear Algebra and its Applications, 2016, vol. 494, pp. 70–79. https://doi.org/10.1016/j.laa.2016.01.005Бенедиктович, В. И. Спектральный радиус сбалансированного двудольного графа и его гамильтоновость / В. И. Бенедиктович // Докл. Нац. акад. наук Беларуси. – 2017. – т. 61, № 2. – С. 7–12.Benediktovich V. I. Spectral radius of a balanced bipartite graph and its Hamiltonicity. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2017, vol. 61, no. 2, pp. 7–12 (in Russian).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.1580668Ge J., Ning B. Spectral radius and Hamiltonian properties of graphs, II. Linear and Multilinear Algebra, 2019, pp. 1–18. https://doi.org/10.1080/03081087.2019.1580668Bondy, 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-5Bondy J. A. Pancyclic graphs I. Journal of Combinatorial Theory, Series B, 1971, vol. 11, no. 1, pp. 80–84. https://doi.org/10.1016/0095-8956(71)90016-5Копылов, Г. Н. О максимальных путях и циклах в графе / Г. Н. Копылов // Докл. Акад. наук СССР. – 1977. – т. 234, № 1. – С. 19–21.Kopylov G. N. Maximal paths and cycles in a graph. Doklady Akademii nauk SSSR [Doklady of the Academy of Sciences of the USSR], 1977, vol. 234, no. 1, pp. 19–21 (in Russian).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-gHong Y. Bounds of eigenvalues of graphs. Discrete Mathematics, 1993, vol. 123, no. 1–3, pp. 65–74. https://doi.org/10.1016/0012-365x(93)90007-gHong, 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.1997Hong Y., Shu J., Fang K. A sharp upper bound of the spectral radius of graphs. Journal of Combinatorial Theory, Series B, 2001, vol. 81, no. 2, pp. 177–183. https://doi.org/10.1006/jctb.2000.1997Feng, 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/pim0999035fFeng L., Yu G. On three conjectures involving the signless Laplacian spectral radius of graphs. Publications de l’Institut Mathématique, 2009, vol. 85, no. 99, pp. 35–38. https://doi.org/10.2298/pim0999035f

The authors declare that there are no conflicts of interest present.