In this paper we estimate the number of permutations realizable in fault-tolerant multistage interconnection networks designed to tolerate faults on any switching element. The Parallel Omega network and the INDRA network are representative types of fault-tolerate multistage interconnection networks designed to tolerate a single fault. In order to evaluate the enhancement in the function of network by preparing the hardware redundancy for fault-tolerance, we estimate the number of permutations realizable in fault-tolerant networks. This result enables us to set up a standard to evaluate the hardware redundancy required to tolerate multifaults from the viewpoint of the enhancement of network function. This paper concludes that in the case where the number of inputs is up to 32 the increase ratio of the number of realizable permutations is no more than 1/0.73 even if the tolerance to multifaults is prepared instead of the tolerance to a single fault.

Some properties of an optimum set of paths which pass all arcs of a graph are presented. It is shown that the unique existence of the optimum set depends on the configuration of a graph. The set is of use as the minimum set of test cases to the path test.

This paper presents an optimum design method of reliable networks. This paper, first, discusses several design methods for undirected graphs. It is shown that one new method of them gives graphs with the minimum diameter in a certain domain. In order to obtain optimum graph when the number of nodes and degree are given, this paper next discusses a method to obtain modified graphs with larger connectivity and also with the minimum diameter from known graphs which have diameter 1 over the minimum.