On the multipacking number of grid graphs
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 multi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4452/pdf |
| _version_ | 1827323771737866240 |
|---|---|
| author | Laurent Beaudou Richard C. Brewster |
| author_facet | Laurent Beaudou Richard C. Brewster |
| author_sort | Laurent Beaudou |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:52Z |
| format | Article |
| id | doaj.art-cb4eea2020e54d3f890dbe8722707700 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:52Z |
| publishDate | 2019-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-cb4eea2020e54d3f890dbe87227077002024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-06-01Vol. 21 no. 3Graph Theory10.23638/DMTCS-21-3-234452On the multipacking number of grid graphsLaurent BeaudouRichard C. BrewsterIn 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.https://dmtcs.episciences.org/4452/pdfcomputer science - discrete mathematicsmathematics - combinatorics |
| spellingShingle | Laurent Beaudou Richard C. Brewster On the multipacking number of grid graphs Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics mathematics - combinatorics |
| title | On the multipacking number of grid graphs |
| title_full | On the multipacking number of grid graphs |
| title_fullStr | On the multipacking number of grid graphs |
| title_full_unstemmed | On the multipacking number of grid graphs |
| title_short | On the multipacking number of grid graphs |
| title_sort | on the multipacking number of grid graphs |
| topic | computer science - discrete mathematics mathematics - combinatorics |
| url | https://dmtcs.episciences.org/4452/pdf |
| work_keys_str_mv | AT laurentbeaudou onthemultipackingnumberofgridgraphs AT richardcbrewster onthemultipackingnumberofgridgraphs |