Partition connectivity

Graphs

Let G=(V,E) be an undirected graph. For an integer k, G is said to be k-partition-connected if for every partition [math]{\mathcal P}[/math] of V there are at least [math]k(|{\mathcal P}|-1)[/math] edges in E that connect different classes of [math]{\mathcal P}[/math]. By Tutte's theorem this is equivalent to the property that G can be decomposed into k connected spanning subgraphs.

Hypergraphs

A similar definition can be given for hypergraphs. Let H=(V,E) be a hypergraph and k a positive integer. H is called k-partition-connected if for every partition [math]{\mathcal P}[/math] of V there are at least [math]k(|{\mathcal P}|-1)[/math] hyperedges in E that are not induced by a class of [math]{\mathcal P}[/math]. A 1-partition-connected hypergraph is also called partition-connected (note that not all connected hypergraphs are partition-connected).

Frank, Király and Kriesell proved the following characterization: A hypergraph is k-partition-connected if and only if it can be decomposed into k partition-connected spanning sub-hypergraphs. In contrast, for any k there are k-edge-connected hypergraphs that cannot be decomposed into 2 connected spanning sub-hypergraphs .

(k,l)-partition-connectivity

One useful generalization is the following: a hypergraph H=(V,E) is (k,l)-partition-connected for non-negative integers k and l if for every non-trivial partition [math]{\mathcal P}[/math] of V there are at least [math]k(|{\mathcal P}|-1)+l[/math] hyperedges in E that are not induced by a class of [math]{\mathcal P}[/math]. Note that (0,l)-partition-connectivity is equivalent to l-edge-connectivity.