Well-balanced orientations of hypergraphs
When can we characterize hypergraphs that have an orientation satisfying a prescribed symmetric local edge-connectivity requirement? Special case: can we characterize hypergraphs that have an orientation which is k-edge-connected within a specified subset of nodes?
Frank, Király and Király proved an extension of Nash-Williams' weak orientation theorem by characterizing hypergraphs which have a k-edge-connected orientation. In this result "orienting a hypergraph" means picking a head node from each hyperedge.
For the same definition of hypergraph orientation, Király and Lau proved that if a hypergraph H is 2k-edge-connected within a subset T of nodes, then for any [math]r \in T[/math] it has an orientation where from any node of T there are k edge-disjoint paths to r.
To extend the strong orientation theorem of Nash-Williams to hypergraphs, one may need a different definition of hypergraph orientation. This may be related to the open problem on Highly element-connected orientation of graphs.
- A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Applied Mathematics. 131 (2003) 385--400. DOI link. EGRES Technical Report no. 2001-06
- T. Király, L.C. Lau, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Journal of Combinatorial Theory B 98 (2008), 1233-1252. DOI link. EGRES Technical Report no. 2006-13
- C. St. J. A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567.