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-2022-58-2-169-178vestifm-641Research ArticleМАТЕМАТИКАMATHEMATICSСпектральные достаточные условия существования максимальной цепи в графе и его трассируемостьSpectral sufficient conditions of the existence of the longest path in the graph and its traceabilityБенедиктовичВ. И.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 Belarus202205072022582169178Copyright © Бенедиктович В.И., 20222022Бенедиктович В.И.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/641

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

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.

гамильтоновостьтрассируемостьматрица смежностибеззнаковая матрица Лапласа(κτ)-регулярное множествоспектрглавный спектрспектральный радиус графаHamiltonicitytraceabilityadjacency matrixsignless Laplace matrix(κτ)-regular setspectrummain spectrumspectral radius of a graphРабота профинансирована Инсти тутом математики НАН Беларуси в рамках Государственной программы фундаментальных исследований «Конвергенция 2025» и Белорусским республиканским фондом фундаментальных исследований (проект № Ф20УКА–005).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).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.Бенедиктович, В. И. Собственные значения, трассируемость и совершенное паросочетание графа / В. И. Бенедиктович // Вес. Нац. акад. навук Беларусі. Сер. фіз.-мат. навук. – 2021. – Т. 57, № 3. – С. 274–285. https://doi.org/10.29235/15612430-2021-57-3-274-285Benediktovich 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Копылов, Г. Н. О максимальных путях и циклах в графе / Г. Н. Копылов // Докл. Акад. наук СССР. – 1977. – Т. 234, № 1. – С. 19–21.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).Hong, Y. A sharp upper bound of the spectral radius of graphs / Y. Hong, J. Shu, K. Fang // J. Comb. Theory. Ser. B. – 2001. – Vol. 81, № 2. – P. 177–183. https://doi.org/10.1006/jctb.2000.1997Hong 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.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-5Cardoso, 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-24302020-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-407Cvetković, D. Spectral generalizations of line graphs / D. Cvetković, P. Rowlinson, S. Simić // London Mathematical Society Lecture Note Series. – Cambridge University Press, 2004. – Vol. 314. https://doi.org/10.1017/cbo9780511751752Cvetković 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

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