UPP graphs and UMFA networks-architecture for parallel systems

A graph with unique path property (UPP) has 2ⁿ vertices and a unique path of length n between every two vertices. These graphs are very important in the design of architectures and algorithms for interconnection networks. Given two UPP graphs, an algorithm is introduced to determine isomorphism between the graphs. A construction is given for nonisomorphic UPP graphs and a lower bound of 2^x, where x=(2ⁿ⁺¹-3-2)/9, nonisomorphic graphs with 2ⁿ vertices is shown. UMFA (uniform minimal full access) networks are multistage interconnection networks that use the same interconnection pattern between every two consecutive stages. These networks are derived from UPP graphs, and the most known network of this type is the Omega network. The problem of rearrangeability of UMFA networks is discussed