Distance spectral radius and Hamiltonicity of a graph
https://doi.org/10.29235/1561-2430-2023-59-1-62-70
Abstract
In recent years, the eigenvalues of the distance matrix of a graph have attracted a lot of attention of mathematicians, since there is a close connection between its spectrum and the structural properties of the graph. Thus, quite recently an interesting result was obtained, relating the Hamiltonicity of a graph to the distance spectral radius of the graph, on the basis of which a more general conjecture about the Hamiltonicity of a graph was formulated. We confirm this conjecture put forward for a k-connected graph, when k Î{2;3}, and also establish similar sufficient conditions for the traceability of a k-connected graph, when k Î{1; 2}.
Keywords
k-connectivity,
Hamiltonicity,
traceability of a graph,
distance matrix of a graph,
distance spectral radius of a graph
Supporting agencies: This work was funded by the Institute of Mathematics of the National Academy of Sciences of Belarus within the framework of “Convergence 2025” State Program for Scientific Research.
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 Ma- thematics), Leading Researcher
Surganov Str., 11, 220072, Minsk
References
1. Godsil C. Algebraic Combinatorics. New York, Routledge, 2017. 368 p. https://doi.org/10.1201/9781315137131
2. Huiqiu Lin, Yuke Zhang. Extremal problems on distance spectra of graphs. Discrete Applied Mathematics, 2021, vol. 289, pp. 139–147. https://doi.org/10.1016/j.dam.2020.09.023
3. Prasolov V. V. Polynomials. 2nd ed. Moscow, MTsNMO Publ., 2001. 336 p. (in Russian).
4. Bose S. S., Nath M., Paul S. On the maximal distance spectral radius of graphs without a pendent vertex. Linear Algebra and its Applications, 2013, vol. 438, no. 11, pp. 4260–4278. https://doi.org/10.1016/j.laa.2013.01.019
5. Zhou Q., Broersma H., Wang L., Lu Y. On sufficient spectral radius conditions for hamiltonicity of k-connected graphs. Linear Algebra and its Applications, 2020, vol. 604, pp. 129–145. https://doi.org/10.1016/j.laa.2020.06.012
6. Bondy J. A., Chvátal V. A method in graph theory. Discrete Mathematics, 1976, vol. 15, no. 2, pp. 111–135. https://doi.org/10.1016/0012-365x(76)90078-9
Review
Views: 333
Email this article 