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, called 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ⁿ+2^k, 0⩽k⩽n, are derived. Interestingly, traffic density over links in such an incomplete hypercube is found to 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