A note on the invertibility of oriented graphs

Natalie Behague¹ ; Tom Johnston² ; Natasha Morrison³ ; Shannon Ogden³

¹University of Warwick
²University of Bristol
³University of Victoria

The electronic journal of combinatorics, Tome 32 (2025) no. 1

Résumé

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 $\text{inv}(D)$, to be the minimum number of inversions required to obtain an acyclic oriented graph from $D$. The dijoin, denoted $D_1\rightarrow 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 $\text{inv}({D_1 \rightarrow D_2}) > \text{inv}(D_1)$, for any oriented graphs $D_1$ and $D_2$ such that $\text{inv}(D_1) = \text{inv}(D_2) \ge 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.

Détail

DOI : 10.37236/13018

Classification : 05C20