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)) ≤ ... ≤ λ1(L(G)) satisfy
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]