A case of the dijoin conjecture on inverting oriented graphs

A case of the dijoin conjecture on inverting oriented graphs

Mathematics

Patrick Gaudart-Wifling

2025

Natalie Behague

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( D 1 → D 2) = inv( D 1) + inv( D 2), is true in the case where inv( D 1) = 2 and inv( D 2) is even. We also characterise the cases inv( D 1) = 2 and inv( D 2) 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.

Combinatorics, Graph Theory, Extremal Problems