Brouwer's conjecture

In the mathematical field of spectral graph theory, Brouwer's conjecture is a conjecture by Andries Brouwer on upper bounds for the intermediate sums of the eigenvalues of the Laplacian of a graph in term of its number of edges.^[1]

The conjecture states that if G is a simple undirected graph and L(G) its Laplacian matrix, then its eigenvalues λ_n(L(G)) ≤ λ_n−1(L(G)) ≤ ... ≤ λ₁(L(G)) satisfy

$${\displaystyle \sum _{i=1}^{t}\lambda _{i}(L(G))\leq m(G)+\left({\begin{array}{c}t+1\\2\end{array}}\right),\quad t=1,\ldots ,n}$$

State of the art

Brouwer has confirmed by computation that the conjecture is valid for all graphs with at most 10 vertices.^[1] It is also known that the conjecture is valid for any number of vertices if t = 1, 2, n − 1, and n.

For certain types of graphs, Brouwer's conjecture is known to be valid for all t and for any number of vertices. In particular, it is known that is valid for trees,^[2] and for unicyclic and bicyclic graphs.^[3] It was also proved that Brouwer’s conjecture holds for two large families of graphs; the first family of graphs is obtained from a clique by identifying each of its vertices to a vertex of an arbitrary c-cyclic graph, and the second family is composed of the graphs in which the removal of the edges of the maximal complete bipartite subgraph gives a graph each of whose non-trivial components is a c-cyclic graph.^[4] For certain sequences of random graphs, Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity.^[5]

References

This page was last edited on 8 May 2024, at 07:54