1. On generation of a class of flowgraphs
- Author
-
Hurkens, A. J.C., Hurkens, C. A.J., Whitty, R. W., Nesetril, J., Fiedler, M., and Discrete Mathematics
- Subjects
Combinatorics ,Discrete mathematics ,Flowchart ,law ,Binary number ,Digraph ,law.invention ,Mathematics ,Vertex (geometry) - Abstract
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.
- Published
- 1992