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}) |
Theorem: For any cubical graph G,
In general, eden(G,d) is not monotone. For example, if G is just a square (=Q_{2}), then eden(G,2) = 1 but eden(G,3) = 2/3. However,
Theorem: For any cubical graph G and dimension d,
For trees and cycles, much stronger results are possible:
Theorem:
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.
Copyright © 2005-2016 Quentin F. Stout |