# 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 ^{[1]} 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 ^{[2]}.

### (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.

## References

- ↑ A. Frank, T. Király, M. Kriesell,
*On decomposing a hypergraph into k connected sub-hypergraphs*, Discrete Applied Mathematics 131 (2003), 373-383. DOI link, EGRES Technical Report - ↑ J. Bang-Jensen, S. Thomassé,
*Highly connected hypergraphs containing no two edge-disjoint spanning connected subhypergraphs*, Discrete Applied Mathematics 131 (2003), 555-559. DOI link