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)) ≤ ... ≤ λ1(L(G)) satisfy [math]\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 }[/math] 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
- ↑ 1.0 1.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.
- ↑ Haemers, W.H.; Mohammadian, A.; Tayfeh-Rezaie, B. (2010). "On the sum of Laplacian eigenvalues of graphs" (in en). 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" (in en). 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" (in en). Linear Algebra and Its Applications 588 (1): 1–18. doi:10.1016/j.laa.2019.11.020. https://www.sciencedirect.com/science/article/abs/pii/S0024379519304963.
- ↑ Rocha, Israel (2020). "Brouwer's conjecture holds asymptotically almost surely" (in en). Linear Algebra and Its Applications 597: 198–205. doi:10.1016/j.laa.2020.03.019.
 |  |
