Strength of a graph

<h2 id="definitions">Definitions</h2>
<p>The strength 
  
    
      
        σ
        (
        G
        )
      
    
    {\displaystyle \sigma (G)}
  
 of an undirected <a href="/facts/Simple_graph/kw3eIBUe">simple graph</a> <i>G</i> = (<i>V</i>, <i>E</i>) admits the three following definitions:
</p>
<ul><li>Let 
  
    
      
        Π
      
    
    {\displaystyle \Pi }
  
 be the set of all <a href="/facts/Partition_of_a_set/VeP9g8CA">partitions</a> of 
  
    
      
        V
      
    
    {\displaystyle V}
  
, and 
  
    
      
        ∂
        π
      
    
    {\displaystyle \partial \pi }
  
 be the set of edges crossing over the sets of the partition 
  
    
      
        π
        ∈
        Π
      
    
    {\displaystyle \pi \in \Pi }
  
, then  
  
    
      
        
          σ
          (
          G
          )
          =
          
            min
            
              π
              ∈
              Π
            
          
          
            
              
                
                  |
                
                ∂
                π
                
                  |
                
              
              
                
                  |
                
                π
                
                  |
                
                −
                1
              
            
          
        
      
    
    {\displaystyle \displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}}
  
.</li>
<li>Also if 
  
    
      
        
          
            T
          
        
      
    
    {\displaystyle {\mathcal {T}}}
  
 is the set of all spanning trees of <i>G</i>, then</li></ul>

σ
        (
        G
        )
        =
        max
        
          {
          
            
              ∑
              
                T
                ∈
                
                  
                    T
                  
                
              
            
            
              λ
              
                T
              
            
             
            :
             
            ∀
            T
            ∈
            
              
                T
              
            
             
            
              λ
              
                T
              
            
            ≥
            0
            
              
                 and 
              
            
            ∀
            e
            ∈
            E
             
            
              ∑
              
                T
                ∋
                e
              
            
            
              λ
              
                T
              
            
            ≤
            1
          
          }
        
        .
      
    
    {\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}

<ul><li>And by <a href="/facts/Linear_programming/GduXFQxT">linear programming</a> duality,</li></ul>

σ
        (
        G
        )
        =
        min
        
          {
          
            
              ∑
              
                e
                ∈
                E
              
            
            
              y
              
                e
              
            
             
            :
             
            ∀
            e
            ∈
            E
             
            
              y
              
                e
              
            
            ≥
            0
            
              
                 and 
              
            
            ∀
            T
            ∈
            
              
                T
              
            
             
            
              ∑
              
                e
                ∈
                E
              
            
            
              y
              
                e
              
            
            ≥
            1
          
          }
        
        .
      
    
    {\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}

<h2 id="complexity">Complexity</h2>
<p>Computing the strength of a graph can be done in <a href="/facts/Time_complexity/77T62gmf">polynomial time</a>, and the first such algorithm
was discovered by Cunningham (1985). The algorithm with best complexity for computing exactly the strength is due to Trubin (1993), uses the flow decomposition of Goldberg and Rao (1998), in time 
  
    
      
        O
        (
        min
        (
        
          
            m
          
        
        ,
        
          n
          
            2
            
              /
            
            3
          
        
        )
        m
        n
        log
        ⁡
        (
        
          n
          
            2
          
        
        
          /
        
        m
        +
        2
        )
        )
      
    
    {\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))}
  
.
</p>
<h2 id="properties">Properties</h2>
<ul><li>If 
  
    
      
        π
        =
        {
        
          V
          
            1
          
        
        ,
        …
        ,
        
          V
          
            k
          
        
        }
      
    
    {\displaystyle \pi =\{V_{1},\dots ,V_{k}\}}
  
 is one partition that maximizes, and for 
  
    
      
        i
        ∈
        {
        1
        ,
        …
        ,
        k
        }
      
    
    {\displaystyle i\in \{1,\dots ,k\}}
  
, 
  
    
      
        
          G
          
            i
          
        
        =
        G
        
          /
        
        
          V
          
            i
          
        
      
    
    {\displaystyle G_{i}=G/V_{i}}
  
 is the restriction of <i>G</i> to the set 
  
    
      
        
          V
          
            i
          
        
      
    
    {\displaystyle V_{i}}
  
, then 
  
    
      
        σ
        (
        
          G
          
            k
          
        
        )
        ≥
        σ
        (
        G
        )
      
    
    {\displaystyle \sigma (G_{k})\geq \sigma (G)}
  
.</li>
<li>The Tutte-Nash-Williams theorem:  
  
    
      
        ⌊
        σ
        (
        G
        )
        ⌋
      
    
    {\displaystyle \lfloor \sigma (G)\rfloor }
  
 is the maximum number of edge-disjoint spanning trees that can be contained in <i>G</i>.</li>
<li>Contrary to the <a href="/facts/Graph_partition/MSQF0WyD">graph partition</a> problem, the partitions output by computing the strength are not necessarily balanced (i.e. of almost equal size).</li></ul>

<ul><li>W. H. Cunningham. <a href="http://portal.acm.org/citation.cfm?id=3829"><i>Optimal attack and reinforcement of a network,</i></a> J of ACM, 32:549–561, 1985.</li>
<li><a href="/facts/Alexander_Schrijver/eJHJNRGz">A. Schrijver</a>. Chapter 51. <a href="https://www.springer.com/math/applications/book/978-3-540-44389-6"><i>Combinatorial Optimization,</i></a> Springer, 2003.</li>
<li>V. A. Trubin. <a href="https://doi.org/10.1007%2FBF01125543"><i>Strength of a graph and packing of trees and branchings,</i></a>, Cybernetics and Systems Analysis, 29:379–384, 1993.</li></ul>

Strength of a graph open-in-new

Strength of a graph