The authors derive a family of labeled, undirected graphs from the Stirling table of the first kind and investigate properties of these graphs as a basis for multiprocessor interconnection networks. The diameter of a Stirling network with n nodes is ⌈log2(n+1)⌉-1, the average distance is less than 10/3, and the number of links is O(n1’.59). Stirling networks can be inductively specified with incrementability of one, and adjacencies can be determined solely by the node addresses. Many standard networks including full-ringed binary trees, tree machines, meshes and half mesh of trees are shown to be embedded in these combinatorial networks. Properties of Stirling networks are analyzed and related to the underlying mathematical structure. The authors present a routing scheme that is deadlock free, avoids congestions, and can be executed on the fly by bit manipulation of node labels. A methodology for modular construction of these networks yields estimates for the VLSI area required for their layout. Fault-tolerance properties are analyzed, a vulner
