Covering and packing in graphs. V. Mispacking subcubes in hypercubes
type: Item
instance of: scholarly article
title: Covering and packing in graphs. V. Mispacking subcubes in hypercubes
zbMATH Open document ID: 0645.05058
DOI: 10.1016/0898-1221(88)90211-8
author: Niall Graham
author: Frank Harary
publication date: 1988-01-01T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4051680
zbMATH Keywords: node-disjoint packing of a graph
zbMATH Keywords: subgraph
zbMATH Keywords: mispacking
zbMATH Keywords: mispacking numbers
MaRDI profile type: Publication
full work available at URL: 0898-1221(88)90211-8
OpenAlex ID: W1608119071
cites work: COVERING AND PACKING IN GRAPHS, I.
cites work: Covering and packing in graphs IV: Linear arboricity
cites work: Q5572939
cites work: Maximum versus minimum invariants for graphs
published in: Computers & Mathematics with Applications
Recommended article: Q4269451
Recommended article: Q3829583
Recommended article: Q3977499
Recommended article: Packing and covering immersion-expansions of planar sub-cubic graphs
Recommended article: On hypercube packings, blocking sets and a covering problem
Recommended article: On packing and covering numbers of graphs
Recommended article: Packing and Covering Immersion Models of Planar Subcubic Graphs
Recommended article: On packing \(S\)-colorings of subcubic graphs
Recommended article: Covering and packing problems in lattices associated with the \(n\)-cube
Recommended article: Constructions of optimal packing and covering of the complete multigraph with applications
description: scientific article; zbMATH DE number 4051680