Brouwer's conjecture holds asymptotically almost surely

Abstrakt

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 n0 such that if n ≥ n0 then among all 2(n/2) graphs with n vertices, at least (1 − exp (−Cn)) 2(n/2) graphs satisfy Brouwer’s conjecture.