STRUCTURAL AND TREE EMBEDDING ASPECTS OF INCOMPLETE HYPERCUBES

Since the hypercube is not incrementally scalable, a variant hypercube topology with more flexibility in the system size, railed an incomplete hypercube, is examined. An incomplete hypercube may also result from a complete hypercube which operates in a degraded manner after some nodes fail. Elementary properties, including diameter, mean internode distance, and traffic density, of incomplete hypercubes with size 2(n) + 2(k), 0 less than or equal to k less than or equal to n, are derived, Interestingly, traffic density over links in such an incomplete hypercube is found td be bounded by 2 (messages per link per unit time), despite its structural nonhomogeneity, Thus, cube links can easily be constructed so as to avoid any single point of congestion, guaranteeing good performance. The minimum incomplete hypercubes able to embed binary trees with node adjacencies preserved are determined.