# Highly element-connected orientation

Is it true that if an undirected graph *G* with terminal set *T* is *2k*-element-connected, then it has a *k*-element-connected orientation?

## Remarks

An analogous statement for rooted element-connectivity was proved by Király and Lau ^{[1]}. A directed graph *D* with terminal set *T* is **rooted k-element-connected** from [math]r \in T[/math] if there are

*k*element-disjoint paths from

*r*to any other node in

*T*. It is NP-complete to decide if a graph has a rooted

*k*-element-connected orientation

^{[1]}, but Király and Lau proved that if the graph is

*2k*-element-connected, then for any root [math]r \in T[/math] it has a rooted

*k*-element-connected orientation.

Cheriyan and Zou ^{[2]} proved the conjecture for incidence graphs of projective planes, where the terminal set is one side of the bipartition. An important related result is the characterization of graphs having a 2-connected orientation by Thomassen ^{[3]}, see also Characterization of graphs having a k-connected orientation.

## References

- ↑
^{1.0}^{1.1}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 - ↑ J. Cheriyan, C. Zou,
*On orienting graphs for connectivity: Projective planes and Halin graphs*, Operations Research Letters 40 (2012), 337–341, DOI link - ↑ C. Thomassen,
*Strongly 2-connected orientations of graphs*, JCTB 110 (2015), 67-78, DOI link