Diregular Digraphs with Minimum Diameter

Abstract

In recent years many advances in very large scale integrated circuit technology have been made. These have resulted in a growing interest in the design of microprocessor networks. In such networks it is obviously desirable to minimize the distance (i.e., the number of times a message has to be relayed to reach its destination) between any two microprocessors, and thus to reduce the delays and also the load on the interconnecting lines. Ignoring other factors, the smaller the distance between any two microprocessors, the more efficient the network. On the other hand, the cost of the interconnections between the microprocessors increases with the number of lines in the network. Thus it is desirable to have networks with both the minimum distance between any two microprocessors, and the minimum total number of lines. However, if the number of lines is decreased then the distance between the microprocessors tends to increase and vice versa. There seems to be some kind of an inverse relationship between these two criteria of a network, although it is possible that there might be some anomalies.