A characterization of unimodular orientations of simple graphs (Q921013)

Let G be a simple graph, and consider an orientation of the edges of G. Where V is the vertex-set of G, let \(A=(A_{vw}:\) v,w\(\in V)\) be the integral antisymmetric \((0,\pm 1)\)-matrix such that \(A_{vw}=1\) if and only if vw is an edge of G directed from v to w. The orientation of G is said to be unimodular if for every \(W\subseteq V\) the determinant of the submatrix \((A_{vw}:\) v,w\(\in W)\) is 0 or 1. For example the author proved [Discrete Math. 66, 203-208 (1987; Zbl 0647.05039)] that the orientations defined by \textit{W. Naji} [Discrete Math. 54, 329-337 (1985; Zbl 0567.05033)] on circle graphs are regular. For any vertex v and any subset of vertices W let \(\epsilon\) (v,W) be the number of edges leaving v and entering W less the number of edges entering v and leaving W. The main result of this paper says that the orientation of G is unimodular if and only if for every subset of vertices W such that \(\epsilon\) (w,W) is even for every \(w\in W\), we can reverse the orientations of the edges which belong to some cocycle C so that \(| \epsilon (v,W)| \leq 1\) becomes true for every vertex. This generalizes a result of \textit{A. Ghouila-Houri} [C. R. Acad. Sci., Paris 254, 1192-1194 (1962; Zbl 0114.251)] for totally unimodular matrices.