Covering and packing in graphs. V. Mispacking subcubes in hypercubes. (English) Zbl 0645.05058

A node-disjoint packing of a graph G with a subgraph H is a largest collection of disjoint copies of a smaller graph H contained in G; an edge disjoint packing is defined similarly, but no two copies of H have a common edge. Two packing numbers of G with H are defined accordingly. It is easy to determine both of these numbers when H is a subcube of a hypercube G. A mispacking of G with subgraphs H is a minimum maximal collection of disjoint copies of H whose removal from G leaves no subgraph H. Two mispacking numbers of G and H are defined analogously to the packing numbers. Their exact determination is quite difficult but we obtain upper bounds. The covering number of G by a subgraph H is the smallest number of copies of H whose union is all of G. This number is determined for \(G=Q_ n\), \(H=Q_ m\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: DOI


[1] Harary, F., Covering and packing in graphs I, Ann. NY acad. sci., 175, 198-205, (1970) · Zbl 0226.05119
[2] Akiyama, J.; Exoo, G.; Harary, F., Covering and packing in graphs IV: linear arboricity, Networks, 11, 69-72, (1981) · Zbl 0479.05027
[3] Harary, F., ()
[4] Harary, F., Maximum versus minimum invariants for graphs, J. graph theory, 7, 275-284, (1983) · Zbl 0515.05053
[5] J. P. Hayes, T. N. Mudge, Q. F. Stout, S. Colley and J. Palmer. Architecture of a hypercube supercomputer. Proc. 1986 Int. Conf. on Parallel Processing. St. Charles, Illinois (to appear).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.