Problems, proofs, and disproofs on the inversion number
share
The inversion of a set X of vertices in a digraph D consists in reversing the direction of all arcs of D⟨ X⟩. The 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 - 𝒪(√(nlog n)) ≤ 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 k_1,k_2, there exists an integer f(k_1,k_2) such that if D is an oriented graph with inv(D) ≥ f(k_1,k_2) then there is a partition (V_1, V_2) of V(D) such that inv(D⟨ V_i⟩) ≥ k_i 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(k_1,k_2) exists for all pairs of positive integers k_1,k_2 when the oriented graphs in consideration are restricted to be tournaments.
READ FULL TEXT