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-2020-56-4-398-407vestifm-547Research ArticleМАТЕМАТИКАMATHEMATICSГлавные собственные значения графа и его гамильтоновостьMain eigenvalues of a graph and its HamiltonicityБенедиктовичВ. И.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 Belarus202031122020564398–407Copyright © Бенедиктович В.И., 20202020Бенедиктович В.И.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/547

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

The concept of (κ,τ)-regular vertex set appeared in 2004. It was proved that the existence of many classical combinatorial structures in a graph like perfect matchings, Hamiltonian cycles, effective dominating sets, etc., can be characterized by (κ,τ)-regular sets the definition whereof 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. This paper generalizes the well-known properties of (κ,κ)-regular sets of a graph to arbitrary (κ,τ)-regular sets of graphs with an emphasis on their connection with classical combinatorial structures. We also present a recognition algorithm for the Hamiltonicity of the graph that becomes polynomial in some classes of graphs, for example, in the class of graphs with a fixed cyclomatic number.

совершенное паросочетаниегамильтонов циклэффективное доминирующее множествоматрица смежности(κτ)-регулярное множествоглавный спектр графаperfect matchingHamiltonian cycleeffective dominating setadjacency matrix(κτ)-regular setmain spectrum of a graphReferencesГантмахер, Ф. Р. Теория матриц / Ф. Р. Гантмахер. – Физматлит, 2010. – 560 с.Gantmacher F.R. The Theory of Matrices. Fizmatlit Publ., 2010. 560 p. (in Russian).Cvetković, D. A table of connected graphs on six vertices / D. Cvetković, M. Petrić // Discrete Math. – 1984. – Vol. 50. – P. 37–49. https://doi.org/10.1016/0012-365x(84)90033-5Cvetković D., Petrić M. A table of connected graphs on six vertices. Discrete Mathematics, 1984, vol. 50, pp. 37–49. https://doi.org/10.1016/0012-365x(84)90033-5Sciriha, I. Necessary and sufficient conditions for a Hamiltonian graphs / I. Sciriha, D. M. Cardoso // J. Combin. Math. Combin. 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.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.020Cardoso, D. M. Main eigenvalues and (κ,τ)-regular sets / D. M. Cardoso, I. Sciriha, C. Zerafa // Linear Algebra Appl. – 2010. – Vol. 432, № 9. – P. 2399–2408. https://doi.org/10.1016/j.laa.2009.07.039Cardoso D. M., Sciriha I., Zerafa C. Main eigenvalues and (κ,τ)-regular sets. Linear Algebra and its Applications, vol. 432, no. 9, pp. 2399–2408. https://doi.org/10.1016/j.laa.2009.07.039Cvetković, D. Spectral Generalizations of Line Graphs / D. Cvetković, P. Rowlinson, S. Simić. – Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752Cvetković D., Rowlinson P., Simić S. Spectral Generalizations of Line Graphs. Cambridge University Press, 2004. https://doi.org/10.1017/cbo9780511751752

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