A note on inverting the dijoin of oriented graphs

Natalie Behague; Tom Johnston; Natasha Morrison; Shannon Ogden

doi:10.37236/13018

paper

A note on inverting the dijoin of oriented graphs

arXiv:2404.10663 · doi:10.37236/13018

Abstract

For an oriented graph $D$ and a set $X \subseteq V (D)$ , the inversion of $X$ in $D$ is the graph obtained from $D$ by reversing the orientation of each edge that has both endpoints in $X$ . Define the inversion number of $D$ , denoted $inv (D)$ , to be the minimum number of inversions required to obtain an acyclic oriented graph from $D$ . The dijoin, denoted $D_{1} \to D_{2}$ , of two oriented graphs $D_{1}$ and $D_{2}$ is constructed by taking vertex-disjoint copies of $D_{1}$ and $D_{2}$ and adding all edges from $D_{1}$ to $D_{2}$ . We show that $inv (D_{1} \to D_{2}) > inv (D_{1})$ , for any oriented graphs $D_{1}$ and $D_{2}$ such that $inv (D_{1}) = inv (D_{2}) \geq 1$ . This resolves a question of Aubian, Havet, HÃ¶rsch, Klingelhoefer, Nisse, Rambaud and Vermande. Our proof proceeds via a natural connection between the graph inversion number and the subgraph complementation number.

11 pages [version 2: includes minor changes after peer review]