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...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2023-11, Vol.25:2 (Graph Theory)
Main Authors: Slobodin, Aaron, MacGillivray, Gary, Myrvold, Wendy
Format: Article
Language:English
Subjects:
mathematics - combinatorics
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
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
1365-8050
DOI:10.46298/dmtcs.11478