Naturally submodular digraphs and forbidden digraph configurations

In this paper, we present several characterizations of the classes of natur ally submodular digraphs and naturally submodular bi-directed graphs. For e ach class, one characterization is given in terms of forbidden digraph conf igurations and the other in terms of graph decomposition. For the class of bi-directed graphs, an additional characterization in terms of the fixed-or der property is also derived. (C) 2000 Elsevier Science B.V. All rights res erved.