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 |
| _version_ | 1827063335612317696 |
|---|---|
| author | Aaron Slobodin Gary MacGillivray Wendy Myrvold |
| author_facet | Aaron Slobodin Gary MacGillivray Wendy Myrvold |
| author_sort | Aaron Slobodin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:56:34Z |
| format | Article |
| id | doaj.art-991228f54d4a44ceb0bfae8e6bac27e8 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2025-02-18T20:43:53Z |
| publishDate | 2023-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-991228f54d4a44ceb0bfae8e6bac27e82024-10-17T14:17:38ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502023-11-01vol. 25:2Graph Theory10.46298/dmtcs.1147811478Proving exact values for the $2$-limited broadcast domination number on grid graphsAaron SlobodinGary MacGillivrayWendy MyrvoldWe 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.https://dmtcs.episciences.org/11478/pdfmathematics - combinatorics |
| spellingShingle | Aaron Slobodin Gary MacGillivray Wendy Myrvold Proving exact values for the $2$-limited broadcast domination number on grid graphs Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | Proving exact values for the $2$-limited broadcast domination number on grid graphs |
| title_full | Proving exact values for the $2$-limited broadcast domination number on grid graphs |
| title_fullStr | Proving exact values for the $2$-limited broadcast domination number on grid graphs |
| title_full_unstemmed | Proving exact values for the $2$-limited broadcast domination number on grid graphs |
| title_short | Proving exact values for the $2$-limited broadcast domination number on grid graphs |
| title_sort | proving exact values for the 2 limited broadcast domination number on grid graphs |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/11478/pdf |
| work_keys_str_mv | AT aaronslobodin provingexactvaluesforthe2limitedbroadcastdominationnumberongridgraphs AT garymacgillivray provingexactvaluesforthe2limitedbroadcastdominationnumberongridgraphs AT wendymyrvold provingexactvaluesforthe2limitedbroadcastdominationnumberongridgraphs |