On the multipacking number of grid graphs

zbMATH Open1417.05160arXiv1803.09639MaRDI QIDQ5226844FDOQ5226844

Authors: Laurent Beaudou, Richard C. Brewster 

Publication date: 1 August 2019

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.

Full work available at URL: https://arxiv.org/abs/1803.09639

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

zbMATH Keywords

grid graphbroadcast numbermultipacking number

Mathematics Subject Classification ID

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

Cited In (10)

• Grid graphs, Gorenstein polytopes, and domino stackings
• On the complexity of broadcast domination and multipacking In digraphs
• Title not available (Why is that?)
• Broadcast domination and multipacking: bounds and the integrality gap
• 2-limited broadcast domination on grid graphs
• Broadcast Domination in Graphs
• Title not available (Why is that?)
• Relation between broadcast domination and multipacking numbers on chordal graphs
• On 2-limited packings of complete grid graphs
• Broadcasts on paths and cycles

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)