ABSTRACT
An interconnection network connects the processors of the parallel computer. Its architecture can be represented as a graph in which the vertices correspond to the processors and the edges to the communication links. Hence, we use graph and network interchangeably. There are a lot of mutually conflicting requirements in designing the topology of computer networks. It is almost impossible to design a network that is optimal from all aspects. One has to design a suitable network depending on the requirements and their properties. The Hamiltonian properties are one of the major requirements in designing the topology of a network. For example, the Token ring approach is used in some distributed operation systems. An interconnection network requires the presence of Hamiltonian cycles in the structure to meet this approach. Fault-tolerance is also a desirable feature in massive parallel systems that have a relatively high probability of failure. A number of fault-tolerant designs for specific multiprocessor architectures have been proposed based on graph-theoretic models, in which the processor-to-processor interconnection structure is represented by a graph.
