Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00061
Hamilton Decompositions and (n/2)Factorizations of Hypercubes
Vol. 7, no. 1, pp. 7998, 2003. Regular paper.
Abstract Since Q_{n}, the hypercube of dimension n, is known to have n
linkdisjoint paths between any two nodes, the links of Q_{n} can be partitioned
into multiple linkdisjoint 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.

Submitted: November 2001.
Revised: September 2002.
Revised: February 2003.
Communicated by
Balaji Raghavachari

Journal Supporters
