2022/12/18 by Guillaume Aubian, Aubian, Guillaume, Frédéric Havet +11 · 2 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2212.09188
openalex publication_date 2022/12/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The \it inversion of a set X of vertices in a digraph D consists in reversing the direction of all arcs of D⟨X⟩. The \it inversion number of an oriented graph D, denoted by inv(D), is the minimum number of inversions needed to transform D into an acyclic oriented graph. In this paper, we study a number of problems involving the inversion number of oriented graphs. Firstly, we give bounds on inv(n), the maximum of the inversion numbers of the oriented graphs of order n. We show n−O(nlogn−−−−−−√) ≤ inv(n) ≤ n−⌈log(n+1)⌉. Secondly, we disprove a conjecture of Bang-Jensen et al. asserting that, for every pair of oriented graphs L and R, we have inv(L⇒R)=inv(L)+inv(R), where L⇒R is the oriented graph obtained from the disjoint union of L and R by adding all arcs from L to R. Finally, we investigate whether, for all pairs of positive integers k1,k2, there exists an integer f(k1,k2) such that if D is an oriented graph with inv(D)≥f(k1,k2) then there is a partition (V1,V2) of V(D) such that inv(D⟨Vi⟩)≥ki for i=1,2. We show that f(1,k) exists and f(1,k)≤k+10 for all positive integers k. Further, we show that f(k1,k2) exists for all pairs of positive integers k1,k2 when the oriented graphs in consideration are restricted to be tournaments.