Naturally submodular digraphs and forbidden digraph configurations (Q1962020)

The authors present several characterizations of the classes of naturally submodular digraphs and naturally submodular bidirected graphs. For each class, one characterization is given in terms of forbidden digraph configurations and the other in terms of graph decompositions. For the class of bidirected graphs, an additional characterization in terms of the fixed-order property is derived. Specifically, it is shown that naturally submodular digraphs are 1-sums of a certain type of outerplanar digraphs, and naturally submodular bidigraphs can be characterized in terms of the fixed-order property, and that this latter property is not a characteristic of naturally submodular digraphs.