# Characterization of graphs having a k-connected orientation

Is it true that a simple graph *G* has a *k*-connected orientation if and
only if the deletion of any *j<k* nodes leaves a
*2(k-j)*-edge-connected graph?

For [math]k = 2[/math], the conjecture was proved by Carsten Thomassen ^{[1]}. The general conjecture has been disproved by Olivier Durand de Gevigney ^{[2]}. For [math]k \geq 3[/math], he showed that it is NP-complete to decide if a given graph has a *k*-connected orientation. By a slight modification of the proof, he could also show that the problem of deciding the existence of a rooted *k*-connected orientation is NP-complete if [math]k \geq 3[/math].

## Remarks

Gerards ^{[3]} observed that every 4-regular 4-edge-connected graph has a 2-connected orientation. Later Berg and Jordán ^{[4]} proved that the conjecture is true for *k=2* in any Eulerian graph. A simpler proof for this case was found by Király and Szigeti ^{[5]}^{[6]}. The conjecture was verified for Halin graphs by Cheriyan and Zou ^{[7]}.

For general graphs even the *k=2* case was open for a long time. A sufficient condition was found by Jordán ^{[8]}: every 18-connected graph has a 2-connected orientation. This was recently improved to 14-connectivity by Cheriyan, Durand de Gevigney and Szigeti ^{[9]}. The conjecture itself for *k=2* was recently proved by Thomassen ^{[1]}.

The property that the deletion of any *j<k* nodes leaves a *2(k-j)*-edge-connected graph is a special case of [math](n,\lambda)[/math]-connectivity defined by Kaneko and Ota ^{[10]}, and it can be checked in polynomial time.

The following local version of the conjecture follows from the results of Egawa, Kaneko and Matsumo ^{[11]}:

**Theorem.** An undirected graph with two specified nodes *s* and *t* has an orientation in which [math]\kappa(s,t) \geq k[/math] and [math]\kappa(t,s) \geq k[/math] if and only if for every set *X* of *j<k* nodes distinct from *s* and *t*, *G-X* is
*2(k-j)*-edge-connected between *s* and *t*.

## References

- ↑
^{1.0}^{1.1}C. Thomassen,*Strongly 2-connected orientations of graphs*, JCTB 110 (2015), 67-78, DOI link. - ↑ O. Durand de Gevigney,
*On Frank's conjecture on k-connected orientations*, arXiv link. - ↑ A.M.H. Gerards,
*On 2-vertex connected orientations*, manuscript, 1997. - ↑ A. R. Berg, T. Jordán,
*Two-connected orientations of Eulerian graphs*, Journal of Graph Theory 52 (2006),230-242. DOI link, EGRES Technical Report. - ↑ Z. Király, Z. Szigeti,
*Simultaneous well-balanced orientations of graphs*, DOI link. - ↑ Z. Király, Z. Szigeti,
*Reliable Orientations of Eulerian Graphs*, EGRES Technical Reprot no. 2006-01. - ↑ J. Cheriyan, C. Zou,
*On orienting graphs for connectivity: Projective planes and Halin graphs*, Operations Research Letters 40 (2012), 337–341, DOI link. - ↑ T. Jordán,
*On the existence of k edge-disjoint 2-connected spanning subgraphs*, DOI link, EGRES Technical Report. - ↑ J. Cheriyan, O. Durand de Gevigney, Z. Szigeti,
*Packing of Rigid Spanning Subgraphs and Spanning Trees*, arXiv link - ↑ A. Kaneko, K. Ota,
*On minimally (n,λ)-connected graphs*, Journal of Combinatorial Theory, Series B 80 (2000), 156-171. DOI link. - ↑ Y. Egawa, A. Kaneko, M. Matsumoto,
*A mixed version of Menger's theorem*, Combinatorica 11 (1991), 71-74.DOI link.