Packing the Hypercube

• Autorzy: David Offner
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

hypercube; packing; decomposition

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 1
• Strony: 85-93

Daty

wydano

2014-02-01

online

2014-02-14

Twórcy

autor

David Offner

• Department of Mathematics and Computer Science Westminster College, Pennsylvania, USA

Bibliografia

• [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]
• [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]
• [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]
• [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]
• [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]
• [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[Crossref]
• [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]
• [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 [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]
• [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.
• [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 Qn into n isomorphic edge-disjoint trees, Discrete Math. 312 (2012) 1819-1822. doi:10.1016/j.disc.2012.01.033[Crossref][WoS]
• [23] R. Wilson, Decompositions of complete graphs into subgraphs isomorphic to a given graph, Congr. Numer. 15 (1976) 647-659.

Identyfikatory

DOI

10.7151/dmgt.1712