Well-balanced orientations of hypergraphs

From Egres Open
Jump to: navigation, search

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[1] 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[2] 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[3] 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.


  1. 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
  2. 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
  3. C. St. J. A. Nash-Williams, On orientations, connectivity and odd vertex pairings in finite graphs, Canad. J. Math. 12 (1960) 555-567.