Eigenvalues, traceability, and perfect matching of a graph
https://doi.org/10.29235/1561-2430-2021-57-3-274-285
Abstract
It is well known that the recognition problem of the existence of a perfect matching in a graph, as well as the recognition problem of its Hamiltonicity and traceability, is NP-complete. Quite recently, lower bounds for the size and the spectral radius of a graph that guarantee the existence of a perfect matching in it have been obtained. We improve these bounds, firstly, by using the available bounds for the size of the graph for existence of a Hamiltonian path in it, and secondly, by finding new lower bounds for the spectral radius of the graph that are sufficient for the traceability property. Moreover, we develop the recognition algorithm of the existence of a perfect matching in a graph. This algorithm uses the concept of a (κ,τ)-regular set, which becomes polynomial in the class of graphs with a fixed cyclomatic number.
Keywords
Hamiltonicity,
traceability,
perfect matching,
adjacency matrix,
adjacency factor 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 Belarus within the framework of the State Program for Fundamental Research “Convergence” 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. Suil O. Spectral radius and matchings in graphs. Linear Algebra and its Applications, 2021, vol. 614, pp. 316–324. https://doi.org/10.1016/j.laa.2020.06.004
5. 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
6. Yuan Hong, Jin-Long Shu, Kunfu Fang. 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. Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I. Lectures on the Graph Theory. Moscow, Nauka Publ., 1990. 384 p. (in Russian).
9. Brouwer A. E., Haemers W. H. Spectra of Graphs. Springer Universitext, 2012.
10. Prasolov V. V. Polynomials. Moscow, MTsNMO Publ., 2001. 336 p. (in Russian).
11. 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
12. 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
Review
Views: 751
Email this article 