Aaron Slobodin ; Gary MacGillivray ; Wendy Myrvold - Proving exact values for the $2$-limited broadcast domination number on grid graphs

dmtcs:11478 - Discrete Mathematics & Theoretical Computer Science, November 22, 2023, vol. 25:2 - https://doi.org/10.46298/dmtcs.11478
Proving exact values for the $2$-limited broadcast domination number on grid graphsArticle

Authors: Aaron Slobodin ; Gary MacGillivray ; Wendy Myrvold

    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.


    Volume: vol. 25:2
    Section: Graph Theory
    Published on: November 22, 2023
    Accepted on: October 6, 2023
    Submitted on: June 16, 2023
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 136 times.
    This article's PDF has been downloaded 87 times.