On the minimum number of inversions to make a digraph k-(arc-)strong

Zusammenfassung

The inversion of a set X of vertices in a digraph D consists of reversing the direction of all arcs of D(X). We study sinv k (D) (resp. sinv k (D) which is the minimum number of inversions needed to transform D into a k-arc-strong (resp. k-strong) digraph and sinv k (N) = max {sinv k (D) | D is a 2k-edge-connected digraph of order n}. We show : (i) 1/2 log (n-k+1) o;; (ii) for any fixed positive integers k and t, deciding whether a given oriented graph G satisfies sinv k (G) 0, there exists C such that sinv k (T) < C for every tournament T on at least 2k + 1 + Ek vertices.