Packing the Hypercube

Offner, David 

Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 1, pp. 85-93.

Résumé

Let G be a graph that is a subgraph of some n-dimensional hypercube Q_n. For sufficiently large n, Stout [20] proved that it is possible to pack vertex-disjoint copies of G in Q_n so that any proportion r lt; 1 of the vertices of Q_n are covered by the packing. We prove an analogous theorem for edge-disjoint packings: For sufficiently large n, it is possible to pack edge-disjoint copies of G in Q_n so that any proportion r lt; 1 of the edges of Q_n are covered by the packing.

Détail

Keywords: hypercube, packing, decomposition

Bibliographie

[1] W. Aiello and F.T. Leighton, Hamming codes, hypercube embeddings, and fault tolerance, SIAM J. Comput. 37 (2007) 783-803. doi:10.1137/S0097539798332464

[2] B. Barden, R. Libeskind-Hadas, J. Davis, and W. Williams, On edge-disjoint spanning trees in hypercubes, Inform. Process. Lett. 70 (1999) 13-16. doi:10.1016/S0020-0190(99)00033-2

[3] D. Bryant, S. El-Zanati, C. Vanden Eynden, and D. Hoffman, Star decompositions of cubes, Graphs Combin. 17 (2001) 55-59. doi:10.1007/s003730170054

[4] G. Cybenko, D.W. Krumme, and K.N. Venkataraman, Fixed hypercube embedding, Inform. Process. Lett. 25 (1987) 35-39. doi:10.1016/0020-0190(87)90090-1

[5] M.E. Deza, On Hamming geometry of unitary cubes, Cybernetics and Control Theory, Soviet Phys. Dokl. (1961) 940-943.

[6] D. Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combin. Theory (B) 14 (1973) 263-267. doi:10.1016/0095-8956(73)90010-5

[7] A. Felzenbaum, R. Holzman, and D. Kleitman, Packing lines in a hypercube, Discrete Math. 117 (1993) 107-112. doi:10.1016/0095-8956(73)90010-5

[8] J.F. Fink, On the decomposition of n-cubes into isomorphic trees, J. Graph Theory 14 (1990) 405-411. doi:10.1002/jgt.3190140403

[9] M.R. Garey and R.L. Graham, On cubical graphs, J. Combin. Theory (B) 18 (1975) 84-95. doi:10.1016/0095-8956(75)90067-2

[10] V.A. Gorbatov and A.A. Kazanskiy, Characterization of graphs embedded in n-cubes, Engineering Cybernetics, Soviet J. Comput. Systems Sci. 20 (1982) 96-102.

[11] N. Graham and F. Harary, Covering and packing in graphs-V: Mispacking subcubes in hypercubes, Comput. Math. Appl. 15 (1988) 267-270. doi:10.1016/0898-1221(88)90211-8

[12] F. Harary, J. Hayes, and H. Wu, A survey of the theory of hypercube graphs, Comput. Math. Appl. 15 (1988) 277-289. doi:10.1016/0898-1221(88)90213-1

[13] P. Horak, J. Širáň, and W. Wallis, Decomposing cubes, J. Aust. Math. Soc. (A) 61 (1996) 119-128. doi:10.1017/S1446788700000112

[14] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann Publishers, 1991).

[15] M. Livingston and Q. Stout, Embeddings in hypercubes, Math. Comput. Modelling 11 (1988) 222-227. doi:10.1016/0895-7177(88)90486-4

[16] E.M. Palmer, On the spanning tree packing number of a graph: a survey, Discrete Math. 230 (2001) 13-21. doi:10.1016/S0012-365X(00)00066-2

[17] M. Ramras, Symmetric edge-decompositions of hypercubes, Graphs Combin. 7 (1991) 65-87. doi:10.1007/BF01789464

[18] M. Ramras, Symmetric vertex partitions of hypercubes by isometric trees, J. Combin. Theory (B) 54 (1992) 239-248. doi:10.1016/0095-8956(92)90055-3

[19] M. Ramras, Fundamental subsets of edges of hypercubes, Ars Combin. 46 (1997) 3-24.

[20] Q. Stout, Packings in hypercubes, presented at 21st Southeastern Int’l. Conf. on Combinatorics, Graph Theory, and Computing, Boca Raton, FL, (1990). http://www.eecs.umich.edu/~qstout/abs/hyppack.html.

[21] J.H. van Lint, Introduction to Coding Theory, 3rd Edition (Springer, 1998).

[22] S. Wagner and M. Wild, Decomposing the hypercube Q_n into n isomorphic edge-disjoint trees, Discrete Math. 312 (2012) 1819-1822. doi:10.1016/j.disc.2012.01.033

[23] R. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congr. Numer. 15 (1976) 647-659.