# Partition connectivity

## Contents

### 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 ${\mathcal P}$ of V there are at least $k(|{\mathcal P}|-1)$ edges in E that connect different classes of ${\mathcal P}$. 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 ${\mathcal P}$ of V there are at least $k(|{\mathcal P}|-1)$ hyperedges in E that are not induced by a class of ${\mathcal P}$. 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 ${\mathcal P}$ of V there are at least $k(|{\mathcal P}|-1)+l$ hyperedges in E that are not induced by a class of ${\mathcal P}$. Note that (0,l)-partition-connectivity is equivalent to l-edge-connectivity.

## References

1. 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
2. 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