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-3-310-317vestifm-534Research ArticleМАТЕМАТИКАMATHEMATICSАналог гипотезы Брауэра для беззнакового лапласиана кографовAnalogue of Brauer’s conjecture for the signless Laplacian of cographsБенедиктовичВ. И.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 Belarus202018102020563310317Copyright © Бенедиктович В.И., 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/534

Рассматривается класс кографов и его подклассы: пороговые графы и анти-регулярные графы. В 2011 г. Х. Бай подтвердил гипотезу Гроне – Меррис о сумме первых k собственных значений лапласиана произвольного графа. Как вариант указанной гипотезы А. Брауэр выдвинул свою гипотезу о верхней оценке этой суммы, которая хотя и была подтверждена для многих классов графов, однако по-прежнему остается открытой. По аналогии с гипотезой Брауэра в 2013 г. Ф. Ашрафом и другими была предложена гипотеза для суммы k собственных значений беззнакового лапласиана, которая также была впоследствии подтверждена для некоторых классов графов, но остается открытой. В настоящей работе для рассматриваемых нами классов графов подтверждается аналог гипотезы Брауэра для собственных значений их беззнакового лапласиана при некоторых натуральных значениях k, не превосходящих порядка рассматриваемых графов.

In this paper, we consider the class of cographs and its subclasses, namely, threshold graphs and anti-regular graphs. In 2011 H. Bai confirmed the Grone – Merris conjecture about the sum of the first k eigenvalues of the Laplacian of an arbitrary graph. As a variation of the Grone – Merris conjecture, A. Brouwer put forward his conjecture about an upper bound for this sum. Although the latter conjecture was confirmed for many graph classes, however, it remains open. By analogy to Brouwer’s conjecture, in 2013 F. Ashraf et al. put forward a conjecture about the sum of k eigenvalues of the signless Laplacian, which was also confirmed for some graph classes but remains open. In this paper, an analogue of the Brouwer’s conjecture is confirmed for the graph classes under our consideration for the eigenvalues of their signless Laplacian for some natural k which does not exceed the order of the considered graphs.

кографпороговый графанти-регулярный графматрица смежностилапласианбеззнаковый лапласианспектры матрицыcographthreshold graphanti-regular graphadjacency matrixLaplaciansignless Laplacianspectra of matrixРабота выполнена при финансовой поддержке Института математики Национальной академии наук Беларуси в рамках Государственной программы фундаментальных исследований «Конвергенция» и Белорусского республиканского фонда фундаментальных исследований (проект № Ф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).ReferencesHua Bai. Grone-Merris Conjecture / Hua Bai // Trans. Amer. Math. Soc. – 2011. – Vol. 363, № 8. – P. 4463–4474. https://doi.org/10.1090/s0002-9947-2011-05393-6Bai H. Grone-Merris Conjecture. Transactions of the American Mathematical Society, 2011, vol. 363, no. 8, pp. 4463–4474. https://doi.org/10.1090/s0002-9947-2011-05393-6Grone, R. The Laplacian Spectrum of a Graph II / R. Grone, R. Merris // SIAM J. Discr. Math. – 1994. – Vol. 7, № 2. – P. 221–229. https://doi.org/10.1137/s0895480191222653Grone R., Merris R. The Laplacian Spectrum of a Graph II. SIAM Journal on Discrete Mathematics, 1994, vol. 7, no. 2, pp. 221–229. https://doi.org/10.1137/s0895480191222653Brouwer, A. E. Spectra of Graphs / A. E. Brouwer, W. H. Haemers. – New York: Springer, 2012. – 250 р. https://doi.org/10.1007/978-1-4614-1939-6Brouwer A. E., Haemers W. H. Spectra of Graphs. New York, Springer, 2012. 250 p. https://doi.org/10.1007/978-1-4614-1939-6Ashraf, F. On the sum of signless Laplacian eigenvalues of a graph / F. Ashraf, G. R. Omidi, B. Tayfeh-Rezaie // Linear Algebra Appl. – 2013. – Vol. 438, № 11. – P. 4539–4546. https://doi.org/10.1016/j.laa.2013.01.023Ashraf F., Omidi G. R., Tayfeh-Rezaie B. On the sum of signless Laplacian eigenvalues of a graph. Linear Algebra and its Applications, 2013, vol. 438, no. 11, pp. 4539–4546. https://doi.org/10.1016/j.laa.2013.01.023Chvátal, V. Set-packing and threshold graphs. Technical Report Rep., CORR 73–21 / V. Chvátal, P. L. Hammer; Comp. Sci. Dept. Univ. of Waterloo. – Ontario, 1973.Chvátal V., Hammer P. L. Set-packing and threshold graphs. Technical Report Rep., CORR 73–21. Ontario, 1973.Jieshan Yang. On a conjecture for the signless Laplacian eigenvalues / Jieshan Yang, Lihua You // Linear Algebra Appl. – 2014. – Vol. 446. – P. 115–132. https://doi.org/10.1016/j.laa.2013.12.032Yang, J., You L. On a conjecture for the signless Laplacian eigenvalues. Linear Algebra and its Applications, 2014, vol. 446, pp. 115–132. https://doi.org/10.1016/j.laa.2013.12.032

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