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

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. ↑ 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.
Retrieved from "http://lemon.cs.elte.hu/egres/internals/index.php5?title=Characterization_of_graphs_having_a_k-connected_orientation&oldid=2051"