On the submodular matrix representation of a digraph

Abstract

We reexamine the class of (0, ±1) matrices called submodular, which we introduced in (Ann. Discrete Math. 15 (1982) 189). Our key idea in this paper is to define, for each submodular matrix M, a corresponding digraph G whose nodes are the columns of M. Our principal results are as follows: (a) a graph-theoretic interpretation of the polyhedron P(M) = {x: x ≥ 0, Mx ≥ -1}, and (b) for a given G, the description of a submodular matrix contained in all submodular matrices representing G. © 2002 Elsevier Science B.V. All rights reserved.