Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Hamilton Decompositions and (n/2)-Factorizations of Hypercubes
Vol. 7, no. 1, pp. 79-98, 2003. Regular paper.
Abstract Since Qn, the hypercube of dimension n, is known to have n link-disjoint paths between any two nodes, the links of Qn can be partitioned into multiple link-disjoint spanning subnetworks, or factors. We seek to identify factors which efficiently simulate Qn, while using only 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, and 2) mappings (embeddings) of Qn to each of the factors exist, such that the maximum number of links in a factor corresponding to one link in Qn (dilation), is as small as possible. In this paper we consider two algorithms for generating Hamilton decompositions of Qn, and three methods for constructing (n/2)-factorizations of Qn for specific values of n. The most notable (n/2)-factorization of Qn results in two mutually isomorphic factors, each with diameter n + 2, where an embedding exists which maps Qn to each of the factors with constant dilation.
Submitted: November 2001.
Revised: September 2002.
Revised: February 2003.
Communicated by Balaji Raghavachari