Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Brouwer's conjecture
open-in-new
<h2 id="state-of-the-art">State of the art</h2> <p>Brouwer has confirmed by computation that the conjecture is valid for all graphs with at most 10 vertices.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> It is also known that the conjecture is valid for any number of vertices if <i>t</i> = 1, 2, <i>n</i> − 1, and <i>n</i>. </p><p>For certain types of graphs, Brouwer's conjecture is known to be valid for all <i>t</i> and for any number of vertices. In particular, it is known that is valid for trees,<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> and for unicyclic and bicyclic graphs.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> For certain sequences of random graphs, Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="978-1-4614-1938-9" target="_blank">978-1-4614-1938-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>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. <a href="978-1-4614-1938-9" target="_blank">978-1-4614-1938-9</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="https://doi.org/10.1016%2Fj.laa.2009.03.038" target="_blank">https://doi.org/10.1016%2Fj.laa.2009.03.038</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>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. <a href="https://doi.org/10.1016%2Fj.laa.2012.01.007" target="_blank">https://doi.org/10.1016%2Fj.laa.2012.01.007</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="https://doi.org/10.1016%2Fj.laa.2019.11.020" target="_blank">https://doi.org/10.1016%2Fj.laa.2019.11.020</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>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. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>