A characterization of unimodular orientations of simple graphs
type: Item
instance of: scholarly article
title: A characterization of unimodular orientations of simple graphs
zbMATH Open document ID: 0709.05023
DOI: 10.1016/0095-8956(92)90005-I
author: André Bouchet
published in: Journal of Combinatorial Theory. Series B
publication date: 1992-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C50
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 4164901
zbMATH Keywords: orientation
zbMATH Keywords: unimodular matrices
MaRDI profile type: Publication
cites work: Q3490007
cites work: Unimodularity and circle graphs
cites work: Q5722271
cites work: Reconnaissance des graphes de cordes
cites work: Lectures on matroids
description: scientific article; zbMATH DE number 4164901