Let G be a graph that is a subgraph of some n-dimensional hypercube Qn. For sufficiently large n, Stout [20] proved that it is possible to pack vertex- disjoint copies of G in Qn so that any proportion r < 1 of the vertices of Qn 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 Qn so that any proportion r < 1 of the edges of Qn are covered by the packing.
@article{bwmeta1.element.doi-10_7151_dmgt_1712,
author = {David Offner},
title = {Packing the Hypercube},
journal = {Discussiones Mathematicae Graph Theory},
volume = {34},
year = {2014},
pages = {85-93},
zbl = {1285.05149},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1712}
}
David Offner. Packing the Hypercube. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 85-93. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1712/
[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[WoS][Crossref] | Zbl 1144.68008
[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[Crossref] | Zbl 1002.68103
[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[Crossref]
[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[Crossref]
[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[Crossref]
[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[Crossref] | Zbl 0784.05022
[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[Crossref] | Zbl 0735.05063
[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[Crossref] | Zbl 0301.05104
[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. | Zbl 0525.94028
[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[Crossref] | Zbl 0645.05058
[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[Crossref]
[13] P. Horak, J. Širáň, and W. Wallis, Decomposing cubes, J. Aust. Math. Soc. (A) 61 (1996) 119-128. doi:10.1017/S1446788700000112[Crossref] | Zbl 0878.05069
[14] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann Publishers, 1991). | Zbl 0743.68007
[15] M. Livingston and Q. Stout, Embeddings in hypercubes, Math. Comput. Modelling 11 (1988) 222-227. doi:10.1016/0895-7177(88)90486-4 [Crossref]
[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[Crossref]
[17] M. Ramras, Symmetric edge-decompositions of hypercubes, Graphs Combin. 7 (1991) 65-87. doi:10.1007/BF01789464[Crossref] | Zbl 0756.05083
[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[WoS][Crossref]
[19] M. Ramras, Fundamental subsets of edges of hypercubes, Ars Combin. 46 (1997) 3-24. | Zbl 0933.05068
[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). | Zbl 0485.94015
[22] S. Wagner and M. Wild, Decomposing the hypercube Qn into n isomorphic edge-disjoint trees, Discrete Math. 312 (2012) 1819-1822. doi:10.1016/j.disc.2012.01.033[Crossref][WoS] | Zbl 1242.05225
[23] R. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congr. Numer. 15 (1976) 647-659.