Spectral sufficient conditions of the existence of the longest path in the graph and its traceability
https://doi.org/10.29235/1561-2430-2022-58-2-169-178
Abstract
It is known that the existence of many classical combinatorial structures in a graph, such as perfect matchings, Hamiltonian cycles, effective dominating sets, etc., can be characterized using (κ,τ)-regular sets, whose determination is equivalent to the determination of these classical combinatorial structures. On the other hand, the determination of (κ,τ)regular sets is closely related to the properties of the main spectrum of a graph. We use the previously obtained generalized properties of (κ,τ)-regular sets of graphs to develop a recognition algorithm of the traceability of a graph. We also obtained new sufficient conditions for the existence of a longest simple path in a graph in terms of the spectral radius of the adjacency matrix and the signless Laplacian of the graph.
Keywords
Hamiltonicity,
traceability,
adjacency matrix,
signless Laplace matrix,
(κ,τ)-regular set,
spectrum,
main spectrum,
spectral radius of a graph
Supporting agencies: This work was funded by the Institute of Mathematics of the National Academy of Sciences of the Republic of Belarus within the framework of “Convergence” State Program for Fundamental Research and the Belarusian Republican Foundation for Fundamental Research (project no. Ф20УКА–005).
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
Surganov Str., 11, 220072, Minsk
References
1. Cvetković D., Rowlinson P., Simić S. An Introduction to the Theory of Graph Spectra. Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511801518
2. Gantmacher F. R. The Theory of Matrices. Moscow, Fizmatlit Publ., 2010. 560 p. (in Russian).
3. Sciriha I., Cardoso D. M. Necessary and sufficient conditions for a Hamiltonian graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 2012, vol. 80, pp. 127–150.
4. Benediktovich V. I. Eigenvalues, traceability, and perfect matching of a graph. Vestsі Natsyianal’nai akademіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2021, vol. 57, no. 3, pp. 274–285 (in Russian). https://doi.org/10.29235/1561-2430-2021-57-3-274-285
5. Kopylov G. N. Maximal paths and cycles in a graph. Doklady Akademii nauk SSSR = Proceedings of the USSR Academy of Sciences, 1977, vol. 234, no. 1, pp. 19–21 (in Russian).
6. 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
7. Bondy J. A., Murty U. S. R. Graph Theory. New York, Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5
8. Cardoso D. M. An overview of (κ,τ)-regular sets and their applications. Discrete Applied Mathematics, 2019, vol. 269, pp. 2–10. https://doi.org/10.1016/j.dam.2018.12.020
9. Benediktovich V. I. Main eigenvalues of a graph and its Hamiltonicity. Vestsі Natsyianal’nai akademіі navuk Belarusі. Seryia fіzіka-matematychnykh navuk = Proceedings of the National Academy of Sciences of Belarus. Physics and Mathematics series, 2020, vol. 56, no. 4, pp. 398–407 (in Russian). https://doi.org/10.29235/1561-2430-2020-56-4-398-407
10. Cvetković D., Rowlinson P., Simić S. Spectral generalizations of line graphs. London Mathematical Society Lecture Note Series. Vol. 314. Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752
Review
Views: 468
Email this article 