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 $\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$ 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.^[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

^ ^a ^b Brouwer, Andries E.; Haemers, Willem H. (2012). Spectra of Graphs. Universitext. New York, NY: Springer New York. doi:10.1007/978-1-4614-1939-6. ISBN 978-1-4614-1938-9.
^ Haemers, W.H.; Mohammadian, A.; Tayfeh-Rezaie, B. (2010). "On the sum of Laplacian eigenvalues of graphs". Linear Algebra and Its Applications. 432 (9): 2214–2221. doi:10.1016/j.laa.2009.03.038.
^ Du, Zhibin; Zhou, Bo (2012). "Upper bounds for the sum of Laplacian eigenvalues of graphs". Linear Algebra and Its Applications. 436 (9): 3672–3683. doi:10.1016/j.laa.2012.01.007.
^ 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. 588 (1): 1–18. doi:10.1016/j.laa.2019.11.020. S2CID 213564785.
^ Rocha, Israel (2020). "Brouwer's conjecture holds asymptotically almost surely". Linear Algebra and Its Applications. 597: 198–205. arXiv:1906.05368. doi:10.1016/j.laa.2020.03.019. S2CID 189762363.

[:0-1] Brouwer, Andries E.; Haemers, Willem H. (2012). Spectra of Graphs. Universitext. New York, NY: Springer New York. doi:10.1007/978-1-4614-1939-6. ISBN 978-1-4614-1938-9.

[2] Haemers, W.H.; Mohammadian, A.; Tayfeh-Rezaie, B. (2010). "On the sum of Laplacian eigenvalues of graphs". Linear Algebra and Its Applications. 432 (9): 2214–2221. doi:10.1016/j.laa.2009.03.038.

[3] Du, Zhibin; Zhou, Bo (2012). "Upper bounds for the sum of Laplacian eigenvalues of graphs". Linear Algebra and Its Applications. 436 (9): 3672–3683. doi:10.1016/j.laa.2012.01.007.

[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. 588 (1): 1–18. doi:10.1016/j.laa.2019.11.020. S2CID 213564785.

[5] Rocha, Israel (2020). "Brouwer's conjecture holds asymptotically almost surely". Linear Algebra and Its Applications. 597: 198–205. arXiv:1906.05368. doi:10.1016/j.laa.2020.03.019. S2CID 189762363.

[1]

[2]

[3]

[4]

[5]