Spectral conditions of existence of the graph circumference
https://doi.org/10.29235/1561-2430-2019-55-2-169-175
Abstract
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.
Keywords
circumference of graph,
minimum and maximum degree,
adjacency matrix,
unsigned Laplacian of graph,
spectral radius
Supporting agencies: 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.
About the Author
V. I. Benediktovich
Institute of Mathematics of the National Academy of Sciences of Belarus
Belarus
Belarus
Vladimir I. Benediktovich – Ph. D. (Physics and Mathematics), Leading Researcher
11, Surganov Str., 220072, Minsk, Republic of Belarus
References
1. Li 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.1151854
2. Li 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.024
3. Nikiforov 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-y
4. Ning 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.947984
5. Benediktovich 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
6. 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).
7. Ge 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.1580668
8. Bondy 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
9. 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).
10. Hong 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-g
11. Hong 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.1997
12. Feng 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
Review
Views: 910
Email this article 