Packings in Hypercubes

Quentin F. Stout
Computer Science and Engineering, University of Michigan

Abstract: This paper is concerned with the number of copies of a graph that can be packed into a hypercube. Let Q_d denote the d-dimensional hypercube. A graph G is cubical if G can be mapped into a hypercube so that no two vertices of G are mapped to the same vertex of the hypercube, and neighbors in G are mapped to neighbors of the hypercube. Given a cubical graph G,let

vpack(G,d)	= max number of vertex-disjoint copies of G in Q_d
epack(G,d)	= max number of edge-disjoint copies of G in Q_d
vden(G,d)	= vpack(G,d)*(# vertices G) / 2^d
eden(G,d)	= epack(G,d)*(# edges G) / (d2^d-1)

Since the number of vertices in Q_d is 2^d and the number of edges is 2^d-1, vden(G,d) and eden(G,d) represent the fraction of vertices and edges of Q_d that can be covered by disjoint copies of G. I became interested in these packing densities when considering some problems of allocating processors in a hypercube computer, where disjoint tasks (with the same computational requirements) were to be mapped to disjoint processors.

Theorem: For any cubical graph G,

vden(G,d) is a nondecreasing function of d, and
vden(G,d) = 1 - O(C^-d), for some C >1.

Note that this implies that vden(G,d) converges to 1 as d tends to infinity.

In general, eden(G,d) is not monotone. For example, if G is just a square (=Q₂), then eden(G,2) = 1 but eden(G,3) = 2/3. However,

Theorem: For any cubical graph G and dimension d,

If eden(G,d) = eden(G,c) = 1, then eden(G,d+c)) = 1.
If eden(G,d) = 1, then lim eden(G,c) = 1.
If eden(G,d) < 1, then lim eden(G,c) > eden(G,d).

I believe that lim eden(G,c) = 1 for all cubical G, but do not yet have a proof of it.

For trees and cycles, much stronger results are possible:

Theorem:

Let T be a tree of t edges. Then eden(T,t) =1. (This result was independently and nearly simultaneously discovered by John Fink, about 1985).
Let T be a tree of t = k2ⁱ edges, where k is odd. Then eden(T, k*j) = 1 for all j > (i-1)2ⁱ⁺¹ +1.
Let C be a cycle of k edges, where k is even. Then eden(C,k) = 1. (Note that a cycle with an odd number of edges is not cubical.)

Theorem: If G is a graph such that, for each nontrivial biconnected component G' of G there is a c so that eden(G',c) =1, then there is a dimension d such that eden(G,d) = 1.

Finally, note that all of the above results are algorithmic, in that the proofs show how to take a specific embedding and use it to obtain increasingly dense embeddings. For trees and cycles, no initial embedding is needed, as the proof shows how to construct one with the required properties.

Keywords: hypercube, graph embedding, packing, cubical, tree, cycle, biconnected components, graph theory

The paper is still ``in preparation''. Some results were first announced in 1985. This material was presented at the 21st Southeastern Int'l. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, 1990.

Related Work: Here are my papers in graph theory. A particularly relevant paper is Embeddings in hypercubes.