Packing the Hypercube

David Offner

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 1, page 85-93
  • ISSN: 2083-5892

Abstract

top
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.

How to cite

top

David Offner. "Packing the Hypercube." Discussiones Mathematicae Graph Theory 34.1 (2014): 85-93. <http://eudml.org/doc/267849>.

@article{DavidOffner2014,
abstract = {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.},
author = {David Offner},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {hypercube; packing; decomposition},
language = {eng},
number = {1},
pages = {85-93},
title = {Packing the Hypercube},
url = {http://eudml.org/doc/267849},
volume = {34},
year = {2014},
}

TY - JOUR
AU - David Offner
TI - Packing the Hypercube
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 1
SP - 85
EP - 93
AB - 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.
LA - eng
KW - hypercube; packing; decomposition
UR - http://eudml.org/doc/267849
ER -

References

top
  1. [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] Zbl1144.68008
  2. [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] Zbl1002.68103
  3. [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. [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. [5] M.E. Deza, On Hamming geometry of unitary cubes, Cybernetics and Control Theory, Soviet Phys. Dokl. (1961) 940-943. 
  6. [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. [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] Zbl0784.05022
  8. [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] Zbl0735.05063
  9. [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] Zbl0301.05104
  10. [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. Zbl0525.94028
  11. [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] Zbl0645.05058
  12. [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. [13] P. Horak, J. Širáň, and W. Wallis, Decomposing cubes, J. Aust. Math. Soc. (A) 61 (1996) 119-128. doi:10.1017/S1446788700000112[Crossref] Zbl0878.05069
  14. [14] F.T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes (Morgan Kaufmann Publishers, 1991). Zbl0743.68007
  15. [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. [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. [17] M. Ramras, Symmetric edge-decompositions of hypercubes, Graphs Combin. 7 (1991) 65-87. doi:10.1007/BF01789464[Crossref] Zbl0756.05083
  18. [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. [19] M. Ramras, Fundamental subsets of edges of hypercubes, Ars Combin. 46 (1997) 3-24. Zbl0933.05068
  20. [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. [21] J.H. van Lint, Introduction to Coding Theory, 3rd Edition (Springer, 1998). Zbl0485.94015
  22. [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] Zbl1242.05225
  23. [23] R. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congr. Numer. 15 (1976) 647-659. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.