Decomposition of Directed Graphs

Abstract

A composition for directed graphs which generalizes the substitution (or X-join) composition of graphs and digraphs, as well as the graph version of set-family composition, is described. It is proved that a general decomposition theory can be applied to the resulting digraph decomposition. A consequence is a theorem which asserts the uniqueness of a decomposition of any digraph, each member of the decomposition being either indecomposable or “special”. The special digraphs are completely characterized; they are members of a few interesting classes. Efficient decomposition algorithms are also presented.