Talk:Characterization of graphs having a k-connected orientation

Rooted k-connected orientation -- Tamás Király 14:06, 4 June 2010 (UTC)

A necessary condition for the existence of a rooted k-connected orientation can be given using bi-sets. Let G=(V,E) be an undirected graph and let r be the root node. Let [math]\{X^1,\dots,X^t\}[/math] be a family of pairwise independent bi-sets, so that r is not in any of the outer members (this implies that the sets [math]X^i_I[/math] are pairwise disjoint). Then the number of edges in E that cover at least one bi-set in the family must be at least

[math]\sum_{i=1}^t (k-|X^i_O|+|X^i_I|).[/math]

To the best of our knowledge it is open whether this is sufficient for the existence of a rooted k-connected orientation.

Re: Rooted k-connected orientation -- Tamás Király 14:54, 8 July 2010 (UTC)

A stronger necessary condition can be given by redefining independence: two bi-sets can be called independent relative to G if no edge of G can be oriented to cover both. It is clear that the above bound has to hold for families of bi-sets that are pairwise independent relative to G.

Re: Rooted k-connected orientation -- Tamás Király 16:25, 6 May 2013 (UTC)

Recently Olivier Durand de Gevigney proved that the above conditions are not sufficient. The counterexample can be obtained from his NP-completeness proof.