Hamilton Decompositions and (n/2)-Factorizations of Hypercubes

Abstract

Since Q_n, the hypercube of dimension n, is known to have n link-disjoint paths between any two nodes, the links of Q_n can be partitioned into multiple link-disjoint spanning subnetworks, or factors. We seek to identify factors which efficiently simulate Q_n, while using only a portion of the links of Q_n. We seek to identify (n/2)-factorizations, of Q_n where 1) the factors have as small a diameter as possible, and 2) mappings (embeddings) of Q_n to each of the factors exist, such that the maximum number of links in a factor corresponding to one link in Q_n (dilation), is as small as possible. In this paper we consider two algorithms for generating Hamilton decompositions of Q_n, and three methods for constructing (n/2)-factorizations of Q_n for specific values of n. The most notable (n/2)-factorization of Q_n results in two mutually isomorphic factors, each with diameter n + 2, where an embedding exists which maps Q_n to each of the factors with constant dilation.