In graph theory, the strength of an undirected graph corresponds to the minimum ratio of edges removed/components created in a decomposition of the graph in question. It is a method to compute partitions of the set of vertices and detect zones of high concentration of edges, and is analogous to graph toughness which is defined similarly for vertex removal.

Definitions

The strength of an undirected simple graph G=(V,E) admits the three following definitions:

• be the set of all partitions.

• is the set of all spanning trees of G, then

• And by linear programming duality,

Complexity

Computing the strength of a graph can be done in polynomial time.

Properties

• is the restriction of G.

• The Tutte-Nash-Williams theorem is the maximum number of edge-disjoint spanning trees that can be contained in G.

• Contrary to the graph partition problem, the partitions output by computing the strength are not necessarily balanced (i.e. of almost equal size).

References

• W. H. Cunningham. J of ACM, 32:549561, 1985.

• A. Schrijver. Chapter 51. Springer, 2003.

• V. A. Trubin. , Cybernetics and Systems Analysis, 29:379384, 1993.