Brouwer's conjecture holds asymptotically almost surely

Abstract

We show that for a sequence of random graphs Brouwer's conjecture holds true with probability tending to one as the number of vertices tends to infinity. Surprisingly, it was found that a similar statement holds true for weighted graphs with possible negative weights as well. For graphs with a fixed number of vertices, the result implies that there are constants $C>0$ and $n_0$ such that if $n\ge n_0$ then among all $2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ graphs with $n$ vertices, at least $\left(1-\exp \left(-Cn\right)\right)2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}$ graphs satisfy Brouwer's conjecture.