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
