Covering and packing in graphs. V. Mispacking subcubes in hypercubes (Q1102983): Difference between revisions

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