В работе рассматривается проблема построения верхней оценки для суммы максимальных собственных чисел лапласиана графа. Статья посвящена доказательству гипотезы Брауэра, которая состоит в том, что сумма -максимальных собственных чисел лапласиана графа не превышает числа ребер графа плюс \( (t + 1)t⁄2 \). Отметим, что мы доказываем справедливость общей гипотезы Брауэра в предположении справедливости гипотезы для конечного числа графов с числом вершин меньше \( 10^{24 } \), т.е. полное доказательство гипотезы сводится к установлению ее справедливости для конечного числа графов. Доказательство данной гипотезы привлекает интерес большого числа специалистов. Имеется ряд результатов для специальных графов и доказательство справедливости гипотезы для почти всех случайных графов. Рассматриваемое нами доказательство использует индуктивный метод, имеющий ряд особенностей. Оригинальный метод предполагает построение различных оценок для собственных чисел лапласиана, который используется для построения шага индукции. Рассматриваются несколько вариантов метода в зависимости от величин координат собственных векторов лапласиана. Используется известный факт эквивалентности справедливости гипотезы Брауэра для самого графа и дополнения графа.
Abstract. In the article, the authors consider the problem of constructing an upper bound for the sum of the maximal eigenvalues of Laplacian of a graph. The article is devoted to proving the Brouwer conjecture, which states that the sum of the -maximal eigenvalues of Laplacian of a graph does not exceed the number of edges of the graph plus \( (t + 1)t⁄2 \). Note that we prove the validity of the general Brouwer conjecture under the assumption that the conjecture is valid for a finite number of graphs with the number of vertices less than \( 10^{24 } \), i.e., a complete proof of the conjecture is reduced to establishing its validity for a finite number of graphs. The proof of this conjecture attracts the interest of a large number of specialists. There are a number of results for special graphs and a proof of the conjecture for almost all random graphs. The proof we are considering uses an inductive method that has some peculiarities. The original method involves constructing various estimates for the eigenvalues of Laplacian of a graph which is used to construct the induction step. Several variants of the method are considered depending on the values of the coordinates of the eigenvectors of the Laplacian. The well-known fact of equivalence of the validity of the Brouwer conjecture for the graph itself and the complement of the graph is used.
The authors declare that there are no conflicts of interest present.