We present some structure theorems for the class of binary flowgraphs. These graphs show up in the study of the structural complexity of flowcharts. A binary flowgraph is a digraph with distinct vertices s and t such that (1) t is a sink, (2) all vertices other than t have outdegree 2 and (3) for every vertex v there is a path from s to v, and a path from v to t. An irreducible flowgraph (IBF) is a binary flowgraph with no proper subgraph that is a binary flowgraph. We define a simple operation called generation that produces an IBF on k vertices from one on k - 1 vertices. Our main result is that all IBF's can be obtained from an IBF on two vertices by a sequence of generation operations. In some cases the last generation step is uniquely defined and we give some additional results on this matter.
|Title of host publication||Combinatorics, graphs and complexity (Proceedings 4th Czechoslovakian Symposium, Prachatice, Czechoslovakia, 1990)|
|Editors||J. Nesetril, M. Fiedler|
|Place of Publication||Amsterdam|
|Publisher||North-Holland Publishing Company|
|Number of pages||6|
|Publication status||Published - 1992|
|Name||Annals of Discrete Mathematics|