2025/09/12 by Natalie Behague, Behague, Natalie, Patrick Gaudart-Wifling +1
Computer Science · Mathematics · #05C20 #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2509.10232
openalex publication_date 2025/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For an oriented graph D, the inversion of X⊆ V(D) in D is the graph obtained by reversing the orientation of all arcs with both ends in X. The inversion number inv(D) is the minimum number of inversions needed to obtain an acyclic oriented graph. We show that the dijoin conjecture of Bang-Jensen, da Silva and Havet, that inv(D1→ D2)=inv(D1)+inv(D2), is true in the case where inv(D1)=2 and inv(D2) is even. We also characterise the cases inv(D1)=2 and inv(D2) odd, for which the conjecture does and does not hold. We then go on to show a similar result for n-joins, in doing so we prove a conjecture of Alon, Powierski, Savery, Scott and Wilmer. Our proofs build on the idea of tournament minimum rank, introduced by Behague, Johnston, Morrison and Ogden.