Decompositions and orientations of hypergraphs
Jørgen Bang‐Jensen, Stéphan Thomassé · 2001
We consider decompositions of hypergraphs into connected spanning subhypergraphs. We prove that there is no degree of vertex connectivity of a hypergraph $H$ which guaranties that $H$ has two disjoint spanning connected subhypergraphs. A natural extension of edge-connectivity of graphs to edge-connectivity of hypergraphs was given recently by Frank et. al \cite{frankDAMta}. They define a hypergraph $H=(V,E)$ to be $k$-partition-connected if and only if, for every partition of $V$ into non empty sets $V_1,V_2,\ldots{},V_t$, $t\geq 1$, there are at least $k(t-1)$ hyperedges from $E$ which intersect more than one $V_i$. Using an extension of graphic matroids to hypergraphs, it is proved among other things in \cite{frankDAMta} that if a hypergraph is $k$-partition-connected, then $H$ can be decomposed into $k$ edge-disjoint spanning 1-partition-connected (and hence connected) subhypergraphs. In this paper we introduce a version of oriented hypergraphs which we call star hypergraphs. Star hypergraphs are hypergraphs for which every hyperedge has a designated root vertex and thus form a natural extension of digraphs. We study arc-strong connectivity of star hypergraphs and orientations of hypergraphs as star hypergraphs. We prove analogs of Menger''s theorem, Edmond''s theorem on arc-disjoint in-branchings rooted at the same vertex and Robbin''s theorem. We also show that Edmond''s theorem on arc-disjoint out-branchings rooted at the same vertex does not generalize to star hypergraphs. We prove an orientation theorem which characterizes when a hypergraph has an orientation as a star hypergraph in which every subset not containing a prescribed vertex $s$ has out-degree at least $k$. It turns out that the necessary and sufficient condition for this is exactly that $H$ is $k$-partition-connected. Based on this we give a short proof of the result above by Frank et. al. Finally, we also show how to derive a characterization of so-called wooded hypergraphs by Lov\''asz from our strong star hypergraph orientation theorem for hypergraphs. oindent{}{\bf Keywords:} Hypergraph, oriented hypergraph, star hypergraph, decomposition of hypergraphs, edge-connectivity, branchings, orientation, $k$-partition-connected hypergraph, wooded hypergraph.