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-2021-57-3-274-285vestifm-596Research ArticleМАТЕМАТИКАMATHEMATICSСобственные значения, трассируемость и совершенное паросочетание графаEigenvalues, traceability, and perfect matching of a graphБенедиктовичВ. И.BenediktovichV. I.

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

ул. Сурганова, 11, 220072, г. Минск

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

Surganov Str., 11, 220072, Minsk

vbened@im.bas-net.byИнститут математики Национальной академии наук БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus202106102021573274285Copyright © Бенедиктович В.И., 20212021Бенедиктович В.И.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/596

Хорошо известно, что задача распознавания существования в графе совершенного паросочетания, как и задачи распознавания его гамильтоновости и трассируемости, является NP-полной. Совсем недавно были получены нижние оценки на размер и спектральный радиус графа, гарантирующие существование в нем совершенного паросочетания. Мы улучшаем эти оценки, во-первых, благодаря использованию имеющихся оценок на размер графа для существования в нем гамильтоновой цепи, во-вторых, благодаря нахождению новых нижних оценок на спектральный радиус графа, являющихся достаточными для наличия свойства трассируемости. Также приводится алгоритм распознавания существования в графе совершенного паросочетания, использующий понятие (κ,τ)-регулярного множества, который становится полиномиальным в классе графов с фиксированным цикломатическим числом.

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.

гамильтоновостьтрассируемостьсовершенное паросочетаниематрица смежностифактор-матрица смежности(κτ)-регулярное множествоспектрглавный спектрспектральный радиус графаHamiltonicitytraceabilityperfect matchingadjacency matrixadjacency factor matrix(κτ)-regular setspectrummain spectrumspectral radius of a graphРабота профинансирована Институтом математики НАН Беларуси в рамках Государственной программы фундаментальных исследований «Конвергенция» и Белорусским республиканским фондом фундаментальных исследований (проект № Ф20УКА–005).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).ReferencesCvetković, D. An Introduction to the Theory of Graph Spectra / D. Cvetković, P. Rowlinson, S. Simić. – Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511801518Cvetković D., Rowlinson P., Simić S. An Introduction to the Theory of Graph Spectra. Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511801518Гантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. – М.: Физматлит, 2010. – 560 сGantmacher F. R. The Theory of Matrices. Moscow, Fizmatlit Publ., 2010. 560 p. (in Russian)Sciriha, I. Necessary and sufficient conditions for a Hamiltonian graphs / I. Sciriha, D. M. Cardoso // J. Combin. Math. Comb. Comput. – 2012. – Vol. 80. – P. 127–150.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.Suil, O. Spectral radius and matchings in graphs / O. Suil // Linear Algebra Appl. – 2021. – Vol. 614. – P. 316–324. https://doi.org/10.1016/j.laa.2020.06.004Suil 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.004Ning, 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.947984Yuan Hong. A sharp upper bound of the spectral radius of graphs / Yuan Hong, Jin-Long Shu, Kunfu Fang // J. Comb. Theory. Ser. B. – 2001. – Vol. 81, № 2. – P. 177–183. https://doi.org/10.1006/jctb.2000.1997Yuan 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.1997Bondy, J. A. Graph Theory / J. A. Bondy, U. S. R. Murty. – New York: Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5Bondy J. A., Murty U. S. R. Graph Theory. New York, Springer, 2008. https://doi.org/10.1007/978-1-84628-970-5Лекции по теории графов / В. А. Емеличев [и др.]. – М.: Наука, 1990. – 384 с.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).Brouwer, A. E. Spectra of Graphs / A. E. Brouwer, W. H. Haemers. – Springer Universitext, 2012.Brouwer A. E., Haemers W. H. Spectra of Graphs. Springer Universitext, 2012.Прасолов, В. В. Многочлены / В. В. Прасолов. – М.: МЦНМО, 2001. – 336 c.Prasolov V. V. Polynomials. Moscow, MTsNMO Publ., 2001. 336 p. (in Russian).Cardoso, D. M. An overview of (κ,τ)-regular sets and their applications / D. M. Cardoso // Discrete Appl. Math. – 2019. – Vol. 269. – P. 2–10. https://doi.org/10.1016/j.dam.2018.12.020Cardoso 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Бенедиктович, В. И. Главные собственные значения графа и его гамильтоновость / В. И. Бенедиктович // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2020. – Т. 56, № 4. – С. 398–407. https://doi.org/10.29235/1561-2430-2020-56-4-398-407Benediktovich 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

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