Originator(s): Carsten Thomassen, András Frank. (presented by Hehui Wu - REGS 2008)
Definitions: A graph G is weakly 2k-connected if G-X is 2(k-|X|)-edge-connected for every X⊆V(G). We say that vertices u and v are weakly 2k-connected in G if for every set X⊆V(G)-{u,v}, there is a family of 2(k-|X|) edge-disjoint paths in G-X from u to v. Let κw(u,v)=max{2k: u,v is weakly 2k-connected}. A digraph D is k-connected if it has more than k vertices and D-X is strongly connected for all X⊆V with |X|≤k-1.
Conjecture 1 (Thomassen [T]): For all k, there exists a value f(k) such that all f(k)-connected graphs have k-connected orientations.
Conjecture 2 (Frank [F]]): A graph G has a k-connected orientation if and only if G is weakly 2k-edge-connected.
Motivation: Conjecture 2 would be the vertex version of the Nash-Williams Orientation Theorem [N], which states that a graph G has a k-edge-connected orientation if and only if G is 2k-edge-connected.
Conjecture 3 (Wu): Every graph G has an orientation D, such that for all u,v∈V(G), there are &kappaw(u,v)/2 internally disjoint paths from u to v in D.
Comments: Gerards [G] proved Conjecture 2 when k=2 for 4-regular graphs. Berg and Jordán [BJ] extended this (for k=2) by proving it for all Eulerian graphs. Proving Conjecture 2 for Eulerian graphs could be an important step toward the full conjecture. Following Nash-Williams proof of the Orientation Theorem, we could try to prove Conjecture 2 first for Eulerian graphs, then prove Conjecture 3 for Eulerian graphs. Finally, we may be able to use a technique similiar to Nash-williams Vertex Pairing Lemma to complete the proof of Conjecture 2.
References:
[F] A. Frank, Connectivity and Network Flows. Handbook of Combinatorics,
Vol. 1, 2, Elsevier, Amsterdam, (1995), 111--177.
[BJ]A. Berg and T. Jordán, Two-connected orientations of Eulerian
graphs, J Graph Theory 52 (2006), 230--242.
[G] A. M. H. Gerards, On 2-vertex connected orientations, unpublished
manuscript, 1997. See http://homepages.cwi.nl/~bgerards/
[N] C. St. J. A. Nash-Williams, On orientations, connectivity, and odd
vertex pairings in finite graphs, Canad J Math 12 (1960), 555--567.
[T] C. Thomassen, Configurations in graphs of large minimum degree,
connectivity, or chromatic number, Ann NY Acad Sci 555 (1989), 402--412.