Characterization of graphs having a k-connected orientation

From Egres Open
Jump to: navigation, search

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?

Solved b.jpg

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].


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.


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