Brouwer's conjecture

In the mathematical field of <a href="/facts/Spectral_graph_theory/tBttgGTh">spectral graph theory</a>, Brouwer's conjecture is a conjecture by <a href="/facts/Andries_Brouwer/zdSqHqHR">Andries Brouwer</a> on upper bounds for the intermediate sums of the <a href="/facts/Eigenvalues_and_eigenvectors/8TjEoT8u">eigenvalues</a> of the <a href="/facts/Laplacian_matrix/Iwea2mm9">Laplacian</a> of a <a href="/facts/Graph_(discrete_mathematics)/kw3eIBUe">graph</a> in term of its number of edges.
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

∑
          
            i
            =
            1
          
          
            t
          
        
        
          λ
          
            i
          
        
        (
        L
        (
        G
        )
        )
        ≤
        m
        (
        G
        )
        +
        
          (
          
            
              
                
                  t
                  +
                  1
                
              
              
                
                  2
                
              
            
          
          )
        
        ,
        
        t
        =
        1
        ,
        …
        ,
        n
      
    
    {\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}

where m(G) is the number of edges of G.

Brouwer's conjecture open-in-new

Brouwer's conjecture