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 $t$-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.
Fulltext:
PDF file (601 kB)