Proving exact values for the $2$-limited broadcast domination number on grid graphs
We establish exact values for the $2$-limited broadcast domination number of various grid graphs, in particular $C_m\square C_n$ for $3 \leq m \leq 6$ and all $n\geq m$, $P_m \square C_3$ for all $m \geq 3$, and $P_m \square C_n$ for $4\leq m \leq 5$ and all $n \geq m$. We also produce periodically...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2023-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/11478/pdf |
| Summary: | We establish exact values for the $2$-limited broadcast domination number of
various grid graphs, in particular $C_m\square C_n$ for $3 \leq m \leq 6$ and
all $n\geq m$, $P_m \square C_3$ for all $m \geq 3$, and $P_m \square C_n$ for
$4\leq m \leq 5$ and all $n \geq m$. We also produce periodically optimal
values for $P_m \square C_4$ and $P_m \square C_6$ for $m \geq 3$, $P_4 \square
P_n$ for $n \geq 4$, and $P_5 \square P_n$ for $n \geq 5$. Our method completes
an exhaustive case analysis and eliminates cases by combining tools from linear
programming with various mathematical proof techniques. |
|---|---|
| ISSN: | 1365-8050 |