Universal connecting networks and the synthesis of canonical sequential circuits

The problem is treated of finding for a set of identical processing elements an interconnection structure that achieves a certain richness of interelement communication with only a limited number of actual inter-element connections. In graphical terms, this problem is one of finding a universal n-node graph of minimal degree D(n,d) in which every n-node graph of maximum degree d is branchembeddable. This problem is solved in both the undirected and directed cases for small values of d and for small values of n - d, and some general properties of D(n,d) are derived. Interpretation of a directed universal graph as the state graph of a sequential circuit leads to a canonic form for autonomous non-singular networks--that is, a simple network form that is capable of arbitrary autonomous behavior, the specialization being achieved through the selection of a small amount of internal logic.