Analysis of Interconnection Networks Based on Cayley Graphs of Strong Generating Sets

This paper describes a class of interconnection networks based on Cayley graph of (S_n, Omega_CT)> where S_n is the symmetric group of degree n and order n! and Omega_CT is the generator set consisting of all the n (n -1)/2 transpositions, called the complete transposition graph (CTG). A complete enumeration of a set of node disjoint paths for CTG is given which in turn implies that CTG has maximum fault-tolerance.