Brouwer's conjecture explained

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$$\backslash sum\_^\backslash lambda\_(L(G))\backslash leq\; m(G)+\backslash left(\backslash begint+1\backslash \backslash 2\backslash end\backslash right),\backslash quad\; t=1,\backslash 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,^[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]

Notes and References

1. Book: Brouwer. Andries E.. Spectra of Graphs. Haemers. Willem H.. 2012. Springer New York. 978-1-4614-1938-9. Universitext. New York, NY. 10.1007/978-1-4614-1939-6.
2. Haemers. W.H.. Mohammadian. A.. Tayfeh-Rezaie. B.. 2010. On the sum of Laplacian eigenvalues of graphs. Linear Algebra and Its Applications. en. 432. 9. 2214–2221. 10.1016/j.laa.2009.03.038. free.
3. Du. Zhibin. Zhou. Bo. 2012. Upper bounds for the sum of Laplacian eigenvalues of graphs. Linear Algebra and Its Applications. en. 436. 9. 3672–3683. 10.1016/j.laa.2012.01.007. free.
4. Ganie. Hilal A.. Pirzada. S.. Rather. Bilal A.. Trevisan. V. 2020. Further developments on Brouwer's conjecture for the sum of Laplacian eigenvalues of graphs. Linear Algebra and Its Applications. en. 588. 1. 1–18. 10.1016/j.laa.2019.11.020. 213564785 . free.
5. Rocha. Israel. 2020. Brouwer's conjecture holds asymptotically almost surely. Linear Algebra and Its Applications. en. 597. 198–205. 10.1016/j.laa.2020.03.019. 1906.05368. 189762363 .