Laurent Beaudou ; Richard C. Brewster - On the multipacking number of grid graphs

dmtcs:4452 - Discrete Mathematics & Theoretical Computer Science, June 20, 2019, Vol. 21 no. 3 - https://doi.org/10.23638/DMTCS-21-3-23
On the multipacking number of grid graphsArticle

Authors: Laurent Beaudou ; Richard C. Brewster

    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 $\gamma_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) $\leq \gamma_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.


    Volume: Vol. 21 no. 3
    Section: Graph Theory
    Published on: June 20, 2019
    Accepted on: June 7, 2019
    Submitted on: April 20, 2018
    Keywords: Computer Science - Discrete Mathematics,Mathematics - Combinatorics
    Funding:
      Source : OpenAIRE Graph
    • Enumeration on Graphs and Hypergraphs: Algorithms and Complexity; Funder: French National Research Agency (ANR); Code: ANR-15-CE40-0009
    • Metric graph theory; Funder: French National Research Agency (ANR); Code: ANR-17-CE40-0015

    Consultation statistics

    This page has been seen 667 times.
    This article's PDF has been downloaded 286 times.