Strength of a graph: Difference between revisions

In branch of [[mathematics]] called [[graph theory]], the '''strength''' of an undirected [[graphGraph (discrete mathematics)|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 [[Partition of a set|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.

The '''strength''' <math>\sigma(G)</math> of an undirected [[Graph_(mathematics)#Simple_graph|simple graph]] ''G''&nbsp;=&nbsp;(''V'',&nbsp;''E)'') admits the three following definitions:

* Let <math>\Pi</math> be the set of all [[Partition_of_a_setPartition of a set|partitions]] of <math>V</math>, and <math>\partial \pi</math> be the set of edges crossing over the sets of the partition <math>\pi\in\Pi</math>, then <math>\displaystyle\sigma(G)=\min_{\pi\in\Pi}\frac{|\partial \pi|}{|\pi|-1}</math>.

* Also if <math> \mathcal T</math> is the set of all spanning trees of ''G'', then
:: <math>\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\leq1\right\}.</math>

* And by linear programming duality,
:: <math>\sigma(G)=\min\left\{\sum_{e\in E}y_e\ :\ \forall e\in E\ y_e\geq0\mbox{ and }\forall T\in {\mathcal T}\ \sum_{e\in E}y_e\geq1\right\}.</math>

== PropertyProperties ==

* The Tutte-Nash-Williams theorem: <math>\lfloor\sigma(G)\rfloor</math> is the maximum number of edge-disjoint spanning trees that can be contained in ''G''.