2023/03/21 by Julien Duron, Frédéric Havet, Duron, Julien +5
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #VLSI and FPGA Design Techniques #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2303.11719
openalex publication_date 2023/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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) < t (resp. sinv k (G) < t) is NP-complete ; (iii) if T is a tournament of order at least 2k + 1 , then sinv k (T) < sinv k (T) < 2k, and 1/2 log (2k+1) < sinv k (T) < sinv k (T) for some T; (iv) if T is a tournament of order at least 28k - 5 (resp. 14k - 3), then sinv k (T) < 1 (resp. sinv k (T) < 6); (v) for every e > 0, there exists C such that sinv k (T) < C for every tournament T on at least 2k + 1 + Ek vertices.