Local equivalence of directed graphs and monadic second-order logic

Abstract

For a simple directed graph $\It{F}$ if there is an arc from $\It{x}$ to $\It{y}$ for a pair $\It{x}$, $\It{y}$ of distinct vertices, then we call $\It{x}$ an $\It{inneighbor}$ of $\It{y}$ and conversely $\It{y}$ an $\It{outneighbor}$ of $\It{x}$. To locally complement F at a vertex v is for each inneighbor x and outneighbor y of v, to delete the arc (x, y) if there is an arc from $\It{x}$ to $\It{y}$, or to add an arc from x to y otherwise. We say that a directed graph $\It{F}$ is $\It{locally equvalent}$ to another directed graph $\It{H}$ if $\It{H}$ is obtained from F by successive local complementations. Furthermore a directed graph $\It{H}$ is a $\It{vertex-minor}$ of F if H can be obtained by applying a sequence of local complementations and deletions of vertices to $\It{F}$. A. Bouchet introduced Eulerian systems which are related to directed graphs and shows that a pair of directed graphs $\It{F}$, H have same Eulerian system if and only if $\It{H}$ is locally equivalent to F. We show that vertex-minor relation can be expressed in modulo-2 counting monadic second-order logic. This generalizes known properties of local complementations and vertex-minors of undirected graphs to directed graphs.