On the multipacking number of grid graphs

MaRDI QIDQ5226844zbMATH OpenFDO

Authors Laurent Beaudou, Richard C. Brewster

Publication date 1 August 2019

Full work available at URL https://arxiv.org/abs/1803.09639, https://dmtcs.episciences.org/5579/pdf

zbMATH Keywords

broadcast numbergrid graphmultipacking number

Mathematics Subject Classification ID

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

Abstract: In 2001, Erwin introduced broadcast domination in graphs. It is a variant of classical domination where selected vertices may have different domination powers. The minimum cost of a dominating broadcast in a graph $G$ is denoted $gamm{a}_b(G)$. The dual of this problem is called multipacking: a multipacking is a set $M$ of vertices such that for any vertex $v$ and any positive integer $r$, the ball of radius $r$ around $v$ contains at most $r$ vertices of $M$ . The maximum size of a multipacking in a graph $G$ is denoted mp(G). Naturally mp(G) $leqgamm{a}_b(G)$. Earlier results by Farber and by Lubiw show that broadcast and multipacking numbers are equal for strongly chordal graphs. In this paper, we show that all large grids (height at least 4 and width at least 7), which are far from being chordal, have their broadcast and multipacking numbers equal.

Recommendations

• Broadcast domination and multipacking: bounds and the integrality gap
• On the difference between broadcast and multipacking numbers of graphs
• scientific article; zbMATH DE number 6843211
• k-broadcast domination and k-multipacking
• Broadcast domination and multipacking in strongly chordal graphs

Cited in

(17)

• k-broadcast domination and k-multipacking
• On the complexity of broadcast domination and multipacking in digraphs
• Broadcasts on paths and cycles
• Broadcast domination and multipacking in strongly chordal graphs
• On the difference between broadcast and multipacking numbers of graphs
• Broadcast domination in graphs
• scientific article; zbMATH DE number 554182 (Why is no real title available?)
• Broadcast domination and multipacking: bounds and the integrality gap
• On 2-limited packings of complete grid graphs
• scientific article; zbMATH DE number 5238980 (Why is no real title available?)
• 2-limited broadcast domination on grid graphs
• Relation between broadcast domination and multipacking numbers on chordal graphs
• Multipacking in the Euclidean metric space
• On the broadcast independence number of locally uniform 2-lobsters
• Multipacking and broadcast domination on cactus graphs and its impact on hyperbolic graphs
• Relation between broadcast domination and multipacking numbers on chordal and other hyperbolic graphs
• Grid graphs, Gorenstein polytopes, and domino stackings

This page was built for publication: On the multipacking number of grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5226844)