2024/04/23 by Wang, Haozhe, Yang, Yuxuan, Lu, Mei · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2404.14937
For an oriented graph D, the inversion of X ⊆ V(D) in D is the digraph obtained from D by reversing the direction of all arcs with both ends in X. The inversion number of D, denoted by inv(D), is the minimum number of inversions needed to transform D into an acyclic digraph. In this paper, we first show that inv (\overrightarrowC3 ⇒ D)= inv(D) +1 for any oriented graph D with even inversion number inv(D), where the dijoin \overrightarrowC3 ⇒ D is the oriented graph obtained from the disjoint union of \overrightarrowC3 and D by adding all arcs from \overrightarrowC3 to D. Thus we disprove the conjecture of Aubian el at. \cite2212.09188 and the conjecture of Alon el at. \cite2212.11969. We also study the blow-up graph which is an oriented graph obtained from a tournament by replacing all vertices into oriented graphs. We construct a tournament T with order n and inv(T)=(n)/(3)+1 using blow-up graphs.