In the mathematical field of

spectral graph theory In mathematics, spectral graph theory is the study of the properties of a graph in relationship to the characteristic polynomial, eigenvalues, and eigenvectors of matrices associated with the graph, such as its adjacency matrix or Laplacian matrix ...

, Brouwer's conjecture is a conjecture by

Andries Brouwer Andries Evert Brouwer (born 1951) is a Dutch mathematician and computer programmer, Professor Emeritus at Eindhoven University of Technology (TU/e). He is known as the creator of the greatly expanded 1984 to 1985 versions of the roguelike compute ...

on upper bounds for the intermediate sums of the

eigenvalues In linear algebra, an eigenvector () or characteristic vector of a linear transformation is a nonzero vector that changes at most by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted b ...

of the

Laplacian In mathematics, the Laplace operator or Laplacian is a differential operator given by the divergence of the gradient of a scalar function on Euclidean space. It is usually denoted by the symbols \nabla\cdot\nabla, \nabla^2 (where \nabla is the ...

of a graph in term of its number of edges. 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

\sum_^\lambda_(L(G))\leq m(G)+\left(\begin
t+1\\
2
\end\right),\quad t=1,\ldots,n

where ''m''(''G'') is the number of edges of ''G''.

State of the art

Brouwer has confirmed by computation that the conjecture is valid for all graphs with at most 10 vertices. 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, and for unicyclic and bicyclic graphs. 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. For certain sequences of random graphs, Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity.

References

{{Reflist Algebraic graph theory Matrices Conjectures Unsolved problems in graph theory