On generation of a class of flowgraphs

A. J.C. Hurkens, C. A.J. Hurkens, R. W. Whitty

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationCombinatorics, graphs and complexity (Proceedings 4th Czechoslovakian Symposium, Prachatice, Czechoslovakia, 1990)
EditorsJ. Nesetril, M. Fiedler
Place of PublicationAmsterdam
PublisherNorth-Holland Publishing Company
Number of pages6
ISBN (Print)0-444-89543-4
Publication statusPublished - 1992

Publication series

NameAnnals of Discrete Mathematics
ISSN (Print)0167-5060


Dive into the research topics of 'On generation of a class of flowgraphs'. Together they form a unique fingerprint.

Cite this