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

Graham, Niall; Harary, Frank

Comput. Math. Appl. 15, No. 4, 267-270 (1988).

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\).

MSC:

05C70

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Keywords:

node-disjoint packing of a graph; subgraph; mispacking; mispacking numbers

References:

[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).