Аналог гипотезы Брауэра для беззнакового лапласиана кографов

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

кограф, пороговый граф, анти-регулярный граф, матрица смежности, лапласиан, беззнаковый лапласиан, спектры матрицы

1. Hua 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-6

2. Grone, 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/s0895480191222653

3. Brouwer, 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-6

4. Ashraf, 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.023

5. Chvá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.

6. 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.032