Geodesic
On the multipacking number of grid graphs
Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3
Cet article a éte moissonné depuis la source Episciences

Voir la notice de l'article

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. 
@article{DMTCS_2019_21_3_a20,
     author = {Beaudou, Laurent and Brewster, Richard C.},
     title = {On the multipacking number of grid graphs},
     journal = {Discrete mathematics & theoretical computer science},
     year = {2019},
     volume = {21},
     number = {3},
     doi = {10.23638/DMTCS-21-3-23},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-23/}
}
TY  - JOUR
AU  - Beaudou, Laurent
AU  - Brewster, Richard C.
TI  - On the multipacking number of grid graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2019
VL  - 21
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-23/
DO  - 10.23638/DMTCS-21-3-23
LA  - en
ID  - DMTCS_2019_21_3_a20
ER  - 
%0 Journal Article
%A Beaudou, Laurent
%A Brewster, Richard C.
%T On the multipacking number of grid graphs
%J Discrete mathematics & theoretical computer science
%D 2019
%V 21
%N 3
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-21-3-23/
%R 10.23638/DMTCS-21-3-23
%G en
%F DMTCS_2019_21_3_a20
Beaudou, Laurent; Brewster, Richard C. On the multipacking number of grid graphs. Discrete mathematics & theoretical computer science, Tome 21 (2019) no. 3. doi: 10.23638/DMTCS-21-3-23

Cité par Sources :