Folded Petersen cube networks: new competitors for the hypercubes

We introduce and analyze a new interconnection topology, called the k-dimensional folded Petersen (F P_k/) network, which is constructed by iteratively applying the cartesian product on the well-known Petersen graph. Our generalization, the folded Petersen cube F P Q_n,k = Q _n × F P_k/, is a product of the n-dimensional binary hypercube (Q_n) and F P _k/. The P FQ_n,k topology provides regularity, node-and edge-symmetry, optimal connectivity (and therefore maximal fault-tolerance), logarithmic diameter, modularity, and permits self-routing and broadcasting algorithms even in the presence of faults. With the same node-degree and connectivity, F PQ_n,k provides smaller diameter with more nodes and higher packing density than the (n + 3k)-dimensional binary hypercube Q_n+3k. Also F PQ_n,k admits efficient embeddings of many computationally important structures such as rings, meshes, hypercubes, and several tree-related networks