Hamilton Decompositions and (n/2)-Factorizations of Hypercubes - Bass, Douglas; Sudborough, I. Hal (Journal of Graph Algorithms and Applications, 2003)
Since Qn, the hypercube of dimension n, is known to have nlink-disjoint paths between any two nodes, the links of Qn can be partitionedinto multiple link-disjoint spanning subnetworks, or factors. We seekto identify factors which efficiently simulate Qn, while usingonly a portion of the links of Qn. We seek to identify (n/2)-factorizations,of Qn where 1) the factors have as small a diameter as possible, and2) mappings (embeddings) of Qn to each of the factors exist, suchthat the maximum number of links in a factor corresponding to onelink in Qn (dilation), is as small as possible. In this paper weconsider two algorithms for generating Hamilton decompositions of Qn, andthree methods for constructing (n/2)-factorizations of Qn forspecific values of n. The most notable (n/2)-factorization of Qnresults in two mutually isomorphic factors, each with diameter n + 2,where an embedding exists which maps Qn to each of the factors withconstant dilation. <!---->