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 Qd 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 Qd
epack(G,d) = max number of edge-disjoint copies of G in Qd
vden(G,d) = vpack(G,d)*(# vertices G) / 2d
eden(G,d) = epack(G,d)*(# edges G) / (d2d-1)
Since the number of vertices in Qd is 2d and the number of edges is 2d-1, vden(G,d) and eden(G,d) represent the fraction of vertices and edges of Qd 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,

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 (=Q2), then eden(G,2) = 1 but eden(G,3) = 2/3. However,

Theorem: For any cubical graph G and dimension 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: 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.

Quentin F. Stout Home Copyright © 2005-2017 Quentin F. Stout