We introduce and analyze a new interconnection topology, called the k-dimensional folded Petersen (FP/sub k/) network, which is constructed by iteratively applying the Cartesian product operation on the well-known Petersen graph. Since the number of nodes in FP/sub k/ is restricted to a power of ten, for better scalability we propose a generalization, the folded Petersen cube network FPQ/sub n,k/=Q/sub n//spl times/FP/sub k/, which is a product of the n-dimensional binary hypercube (Q/sub n/) and FP/sub k/. The FPQ/sub n,k/ topology provides regularity, node- and edge-symmetry, optimal connectivity (and therefore maximal fault-tolerance), logarithmic diameter, modularity, and permits simple self-routing and broadcasting algorithms. With the same node-degree and connectivity, FPQ/sub n,k/ has smaller diameter and accommodates more nodes than Q/sub n+3k/, and its packing density is higher compared to several other product networks. This paper also emphasizes the versatility of the folded Petersen cube networks as a multicomputer interconnection topology by providing embeddings of many computationally important structures such as rings, multi-dimensional meshes, hypercubes, complete binary trees, tree machines, meshes of trees, and pyramids. The dilation and edge-congestion of all such embeddings are at most two.

We introduce and analyze a new interconnection topology, called the n-dimensional folded Petersen network (FP_n), which is constructed by iteratively applying the cartesian product operation on the well-known Petersen graph itself. The FPn topology provides regularity, node- and edgesymmetry, optimal connectivity (maximal fault-tolerance), logarithmic diameter, and permits self-routing and broad casting algorithms even in the presence of faults. With the same node-degree and connectivity, FPn has smaller diam eter and more nodes than the 3ra-dimensional binary hy percube and several other networks. This paper also em beds rings, meshes, hypercubes, and a variety of tree-related structures efficiently into FP_n.