# Proving exact values for the $2$-limited broadcast domination number on grid
graphs

Aaron Slobodin, Gary MacGillivray, and Wendy Myrvold<EMAIL_ADDRESS>Department of Mathematics and Statistics, University of Victoria, supported by
funding from Natural Sciences and Engineering Research of Council of Canada
<EMAIL_ADDRESS>Department of Mathematics and Statistics, University
of Victoria, supported by funding from<EMAIL_ADDRESS>Department of
Computer Science, University of Victoria, supported by funding from NSERC.

###### Abstract

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.

##  1 Introduction

Suppose there is a transmitter located at each vertex of a graph $G$. A
$k$-limited broadcast $f$ on $G$ is a function
$f:V(G)\mapsto\left\\{0,1,\dots,k\right\\}$. The integer $f(v)$ represents the
strength of the broadcast from $v$, where $f(v)=0$ means the transmitter at
$v$ is not broadcasting. A broadcast of positive strength $f(v)$ from $v$ is
heard by all vertices $u$ such that $d(u,v)\leq f(v)$, where $d(u,v)$ is the
distance between the $u$ and $v$ in $G$. A broadcast $f$ is dominating if each
vertex of $G$ hears the broadcast from some vertex. The cost of a broadcast
$f$ is $\sum_{v\in V(G)}f(v)$. The $k$-limited broadcast domination number
$\gamma_{b,k}(G)$ of a graph $G$ is the minimum cost of a $k$-limited
dominating broadcast on $G$.

The $k$-limited broadcast domination number can be seen to be the optimum
solution to ILP 1.1 shown below. Let $G$ be a graph and fix $1\leq k\leq
rad(G)$, where $rad(G)$ is the radius of $G$. For each vertex $i\in V(G)$ and
$\ell\in\left\\{1,2,\dots,k\right\\}$, let $x_{i,\ell}=1$ if vertex $i$ is
broadcasting at strength $\ell$ and $0$ otherwise.

Minimize: $\displaystyle\sum_{\ell=1}^{k}\sum_{i\in V(G)}\ell\cdot x_{i,\ell}$
(ILP 1.1) Subject to: $\displaystyle(1)\quad\sum_{\ell=1}^{k}\hskip
2.84544pt\sum_{\text{$i\in V(G)\textnormal{ s.t.
}$}\text{$d(i,j)\leq\ell$}}x_{i,\ell}\geq 1,\quad\textnormal{for each vertex
}j\in V(G),$ $\displaystyle(2)\quad
x_{i,\ell}\in\left\\{0,1\right\\}\quad\textnormal{for each vertex }i\in
V(G)\textnormal{ and }\ell\in\left\\{1,2,\dots,k\right\\}.$

The $k$-limited broadcast domination number of a graph was first defined in
Erwin’s 2001 Ph.D. thesis [7] (also see [8]). The first major results for
$k$-limited broadcast domination were given in 2018 and are specific to
$2$-limited dominating broadcasts in trees [3]. These results were generalized
to $k$-limited dominating broadcasts to give a best possible upper bound of
$\gamma_{b,k}(T)\leq\left\lceil\frac{k+2}{k+1}\cdot\frac{n}{3}\right\rceil$,
where $T$ is a tree on $n$ vertices [4]. Specific to $2$-limited dominating
broadcasts, if $G$ is a connected graph of order $n$, then
$\gamma_{b,2}(G)\leq\left\lceil\frac{4n}{9}\right\rceil$ and if $G$ is a graph
of order $n$ that contains a dominating path, then
$\gamma_{b,2}(G)\leq\left\lceil\frac{2n}{5}\right\rceil$ [3]. Yang showed that
if $G$ is a cubic $(C_{4},C_{6})-$free graph of order $n$, then
$\gamma_{b,2}(G)\leq\frac{n}{3}$ [10, 18]. Park recently extended this result
to cubic $C_{4}-$free graph of order $n$ [13].

For each fixed positive integer $k$, the problem of deciding whether there
exists a $k$-limited dominating broadcast of cost at most a given integer $B$
is NP-complete [4, 18]. The results of [18], respectively, establish
$O(n^{3}),$ $O(n^{2}),$ $O(n^{2}),$ and $O(n^{3})$ time algorithms for the
$k$-limited broadcast domination number of strongly chordal graphs, interval
graphs, circular arc graphs, and proper interval bigraphs. The algorithm for
$k$-limited broadcast on strongly chordal graphs in [18] is a specialization
of the $O(n^{3})$ time algorithm for (general) broadcast domination on
strongly chordal graphs in [17, 19].

The $k$-limited broadcast domination problem is a restriction of the broadcast
domination problem in which vertices can broadcast with strength up to
$rad(G)$. The broadcast domination number $\gamma_{b}(G)$ of a graph $G$ is
optimum solution to the ILP obtained from ILP 1.1 by setting $k=rad(G)$. The
broadcast domination number of a graph was introduced in Erwin’s Ph.D. thesis
[7]. Erwin proved that, for every non-trivial connected graph,

$\displaystyle\left\lceil\frac{diam(G)+1}{3}\right\rceil\leq\gamma_{b}(G)\leq\textnormal{
min}\left\\{rad(G),\gamma(G)\right\\}.$

It immediately follows that
$\gamma_{b}(P_{n})=\left\lceil\frac{n}{3}\right\rceil$. Broadcast domination
in trees was first explored in Herke’s M.Sc. thesis [11] (also see [5, 12]).
This work establishes $\gamma_{b}(T)\leq\left\lceil\frac{n}{3}\right\rceil$,
where $T$ is a tree of order $n$. The broadcast domination number is known for
the Cartesian products of two paths [6], two cycles [6], and strong grids [1].
Note that, as $\gamma_{b}\left(C_{m}\square
C_{n}\right)\leq\gamma_{b}\left(P_{m}\square
C_{n}\right)\leq\gamma_{b}\left(P_{m}\square P_{n}\right)$, the previously
stated results provide bounds for $\gamma_{b}\left(P_{m}\square C_{n}\right)$.
A survey of results on broadcast domination can be found in [10].

This paper presents lower bounds for the $2$-limited broadcast domination
number of the Cartesian products of two paths, a path and a cycle, and two
cycles. Our computational approach completes an exhaustive search of all
possible small induced sub-broadcasts of given costs on a graph. Cases which
provably cannot be part of an optimal broadcast are then eliminated. This
approach can likely be extended to other graphs as well as general $k$-limited
broadcast domination.

Some intuition for our method is provided by example in Section 2. Section 3
describes and proves the correctness of the six schemes used to eliminate
cases in the exhaustive search. Section 3 concludes with the statement of our
main algorithm (Algorithm 2) to prove lower bounds and the proof of its
correctness. Our results are summarized in Section 4. These include exact
values for the $2$-limited broadcast domination number of $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$, and
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$. These results improve upon the bounds in Slobodin’s M.Sc.
thesis [14].

##  2 Intuition and Definitions

This section includes a high-level overview of our method, an example specific
to $P_{5}\square C_{n}$, and relevant definitions.

######  Definition 2.1.

Let $f$ be a $2$-limited broadcast on the graph $G$ and let $X\subseteq V(G)$.
Define the sub-broadcast $g$ induced by $X$ by

$\displaystyle g(x)$ $\displaystyle=\begin{cases}f(x)&\textnormal{ if }x\in
X\textnormal{ and }\\\ 0&\textnormal{ otherwise}.\end{cases}$

Throughout this paper, we consider a class of graphs $G_{m,n}$ equal to
$P_{m}\square C_{n}$ or $C_{m}\square C_{n}$ for a fixed number of rows $m$.
In this way, the vertex in the $i$th row and $j$th column can be denoted by
$(i,j)$. The goal is to prove that $\gamma_{b,2}(G_{m,n})$ is greater than or
equal to a function $B(m,n)$. We proceed by induction on $n$. After checking
the appropriate base cases computationally, we assume the bound holds for all
$n<n_{0}$ for some integer $n_{0}$. Let $f$ be a $2$-limited dominating
broadcast of $G_{m,n_{0}}$. We choose values $r$ and $s$ such that, if the
minimum cost (with respect to $f$) of a sub-broadcast induced by $r$
consecutive columns of $G_{m,n_{0}}$ is strictly greater than $s$, then
$B(m,n_{0})\leq\gamma_{b,2}(G_{m,n_{0}})$. We then exhaustively enumerate
(computationally) all possible sub-broadcast induced by $r$ consecutive
columns of $G_{m,n_{0}}$ of cost less than or equal to $s$. If it is possible
to conclude that, for each possible sub-broadcast $g$, either $g$ cannot be a
sub-broadcast of an optimal $2$-limited dominating broadcast on $G_{m,n_{0}}$
or $g$ forces $B(m,n_{0})\leq\gamma_{b,2}(G_{m,n_{0}})$, then the desired
bounds follows. See Example 2.2.

######  Example 2.2.

In [16], the following result is proved.

######  Proposition 2.3.

[16, Theorem 3] For $n\geq 3$, $\gamma_{b,2}\left(P_{5}\square
C_{n}\right)\leq n+\begin{cases}0&\textnormal{for }n\equiv
0\pmod{2}\textnormal{ and}\\\ 1&\textnormal{for }n\equiv
1\pmod{2}.\end{cases}$

Suppose we wish to obtain optimal values for $\gamma_{b,2}(P_{5}\square
C_{n})$ when $n\equiv 0\pmod{2}$ by proving that
$n\leq\gamma_{b,2}(P_{5}\square C_{n})$. We have that
$n\leq\gamma_{b,2}\left(P_{5}\square C_{n}\right)$ for $3\leq n\leq 16$ by
computation. Suppose the bound holds for all $n<n_{0}$ for some $n_{0}>16$.
Let $f$ be a $2$-limited dominating broadcast of $P_{5}\square C_{n_{0}}$. Let
$C$ be the subgraph of $P_{5}\square C_{n_{0}}$ induced by the vertices
appearing in a minimum cost (with respect to $f$) set of eight consecutive
columns (here $r=8$). If the sub-broadcast induced by $V(C)$ has cost at least
8 (here $s=7$), then $cost(f)\geq n_{0}$. It is therefore sufficient to
consider, for each integer $x\leq 7$, all possible sub-broadcasts of cost $x$
induced by $V(C)$. If it is possible to conclude that, for each such sub-
broadcast $g$, either $g$ cannot be a sub-broadcast of an optimal $2$-limited
dominating broadcast on $P_{5}\square C_{n_{0}}$ or $g$ forces
$n_{0}\leq\gamma_{b,2}(P_{5}\square C_{n_{0}})$, then the desired bounds
follows.

We conclude this section with definitions used throughout the rest of the
paper.

######  Definition 2.4.

Given two $2$-limited broadcasts $f$ and $g$ on a graph $G$, for each $x\in
V(G)$, define

$\displaystyle(f\oplus g)(x)=\textnormal{max}\left\\{f(x),g(x)\right\\}$

and

$\displaystyle(f\ominus g)(x)$ $\displaystyle=\begin{cases}0&\textnormal{ if
}g(x)>0\textnormal{ and}\\\ f(x)&\textnormal{ otherwise.}\end{cases}$

######  Definition 2.5.

If $f$ is a broadcast on $G$, then we say $f$ dominates $y\in V(G)$ if there
exists a vertex $x$ such that $f(x)\geq d(x,y)$. Further, we say that $f$
dominates $X\subseteq V(G)$ if it dominates every vertex $x\in X$.

######  Definition 2.6.

Let $f$ be a broadcast on $G$. The broadcast range of $f$ is the set of
vertices which hear a broadcast under $f$.

##  3 Eliminating Possible Induced Sub-broadcasts of Fixed Cost

Fix $m$ and suppose we wish to establish the function $B(n)$ as a lower bound
for the $2$-limited broadcast domination number of $G_{m,n}$. A positive fixed
number $r=r(m)\geq 5$ of columns is chosen. In the inductive step, we consider
$n_{0}>r+10$ such that $B(n)$ is a lower bound for $\gamma_{b,2}(G_{m,n})$ for
all $n<n_{0}$. Let $C$ be the subgraph of $G_{m,n_{0}}$ induced by the
vertices of $r$ consecutive columns. We complete an exhaustive search of all
possible sub-broadcasts $g$ induced by $V(C)$ and subject each such $g$ to a
series of tests in the hope of excluding $g$ or concluding that $g$ forces
$B(n_{0})\leq\gamma_{b,2}(G_{m,n_{0}})$. Given $C$, four columns are added to
both the left and right of $C$ in order to ensure that the subgraph considered
is large enough to include all vertices dominated by any vertex that could
potentially dominate some vertex in $C$.

In summary, our algorithm takes as an input, $H_{m,k}=(P_{m}\textnormal{ or
}C_{m})\square P_{k}$, where $k=r+8$, with columns labelled
$c_{1},c_{2},\dots,c_{k}$, where the vertices of $C$ are in columns
$c_{5},c_{6},\dots,c_{k-4}$. Note that $(P_{m}\textnormal{ or }C_{m})\square
P_{k}$ is understood to mean $P_{m}\square P_{k}$ or $C_{m}\square P_{k}$
dependent upon $G_{m,n}$. Observe that $k\geq 13$ and $n_{0}\geq k+3$. The
assumptions defined previously are used in Sections 3.1 through 3.6 which
describe and prove the correctness of the six schemes we use to eliminate sub-
broadcasts. These schemes appear in the same order as in Algorithm 2 in
Section 3.7.

###  3.1 Domination Requirement

Since we are looking for a lower bound for the cost of an optimal $2$-limited
dominating broadcast $f$ on $G_{m,n_{0}}$, any induced sub-broadcast that
forces vertices of $G_{m,n_{0}}$ to not be dominated, can be eliminated.

######  Observation 1.

If the sub-broadcast $g$ induced by $V(C)$ does not dominate the vertices of
columns $c_{7}$, $c_{8}$, $\dots$, $c_{k-6}$, then $g$ cannot be a sub-
broadcast of a dominating broadcast.

See Figure 1. The region containing $V(C)$ is depicted by the thick black
rectangle. The black circles with a black inner fill indicate vertices
broadcasting at a non-zero strength. The thick red dotted lines indicate the
broadcast ranges of the broadcasting vertices at their centers. In this
example, there is one vertex broadcasting at strength 2 in columns $c_{4}$ and
$c_{k-3}$ and one vertex broadcasting at strength 1 in column $c_{k-3}$. Let
$DoesNotDominate(H_{m,k},g)$ return true if $g$ does not dominate the vertices
of columns $c_{7},c_{8},\dots,c_{k-6}$ and false otherwise.

$c_{2}$$c_{4}$$c_{6}$$c_{1}$$c_{3}$$c_{5}$$c_{7}$$c_{k-6}$$c_{k-4}$$c_{k-2}$$c_{k}$$c_{k-5}$$c_{k-3}$$c_{k-1}$$\dots$$\dots$$\vdots$$\vdots$
Figure 1: The graph $H_{m,k}$ with columns labelled $c_{1},c_{2},\dots,c_{k}$,
$C$ indicated by the thick black rectangle, and possible broadcast vertices
exterior to $C$ which can only dominate vertices in columns
$c_{5},c_{6},c_{k-5},$ and $c_{k-4}$.

###  3.2 Forbidden Broadcasts

To improve the speed of our computations, we have identified four simple
forbidden broadcast structures.

$a)$

$w$$b)$

$w$$c)$

$w$$d)$

Figure 2: Forbidden broadcasts.

Without loss of generality, a sub-broadcast $g$ cannot contain any of the
forbidden broadcasts shown in Figure 2 because the broadcast in $a)$ cannot be
found in an optimal $2$-limited broadcast, and the broadcasts in $b)$, $c)$,
and $d)$ can be replaced by a broadcast of strength 2 from $w$ while
preserving the cost of $g$ and extending the range of $g$. Let
$ForbiddenBroadcast(H_{m,k},g)$ return true if $g$ exhibits $a)$, $b)$, $c)$,
or $d)$ and false otherwise.

###  3.3 Optimality Requirement

As we are attempting to prove a lower bound for the cost of an optimal
$2$-limited dominating broadcast on $G_{m,n_{0}}$, any possible sub-broadcast
that is not optimal can be eliminated.

######  Observation 2.

If the broadcast range $R$ of a possible sub-broadcast $g$ induced by $V(C)$
can be dominated by a broadcast $h$ on $H_{m,k}$ of cost strictly less than
$cost(g)$, then $g$ cannot be a sub-broadcast of an optimal dominating
broadcast.

Let $HasBroadcast(H_{m,k},R,x)$ return true if $R$ can be dominated with cost
less than or equal to $x$ on $H_{m,k}$ and false otherwise.

###  3.4 Proof by Induction

Recall that, after checking the appropriate base cases, we assume $B(n)$ is a
lower bound of $\gamma_{b,2}(G_{m,n})$ for all $n<n_{0}$ where $n_{0}\geq
k+3$. Additionally, the values $r=k-8$ and $s$ are chosen such that, if the
minimum cost of a sub-broadcast induced by $r$ consecutive columns of
$G_{m,n_{0}}$ is strictly greater than $s$, then
$B(n_{0})\leq\gamma_{b,2}(G_{m,n_{0}})$. As such, we may be able to conclude
(via the inductive assumption) that possible sub-broadcasts $g$ of cost less
than or equal to $s$ induced by $r$ consecutive columns of $G_{m,n_{0}}$ imply
the bound we hope to prove. This can be done by deleting $i\leq k$ columns and
“patching” the graph back together to obtain a $2$-limited dominating
broadcast on $G_{m,n_{0}-i}$, the cost of which we assumed to be greater than
or equal to $B(n_{0}-i)$. In general, given some possible induced sub-
broadcast $g$ whose broadcast range $R$ is contained within $k$ consecutive
columns, we delete a particular selection of $i$ columns, for each $i$ from 1
to $k$. To this end, define

$m_{i}=\begin{cases}\max_{n\geq
n_{0}}\left\\{B(n)-B(n-i)\right\\}&\textnormal{ should it exist,}\\\
\infty&\textnormal{otherwise.}\end{cases}$

Algorithm 1 and Lemma 3.1 formalize our approach. See Example 3.2 for an
illustration of this test on $P_{5}\square C_{n}$.

1 function InductiveArgument $(H_{m,k},R,x,m_{1},m_{2},\dots,m_{k})$;

Input : A graph $H_{m,k}=(P_{m}\textnormal{ or }C_{m})\square P_{k}$ with
columns labelled from left to right by $c_{1},c_{2},\dots,c_{k}$, and rows
from 1 to $m$, a set of vertices $R\subseteq V(H_{m,k})$ labelled according to
their row number and column label, the cost $x$ used to dominate $R$ by some
$2$-limited broadcast $g$ whose broadcast range lies entirely within
$H_{m,k}$, and $m_{i}$ (for each $i=1$ to $k$) as defined in Section 3.4.

Output : Value of the truth statement: “sub-broadcast implies bound.”

2 Create a sorted list $L$ of the columns that contain at least one vertex of
$R$ so that they are first ordered from maximum to minimum according to the
number of vertices that are in $R$. Resolve ties by sorting so that $c_{i}$
comes before $c_{j}$ if $i<j$;

3 for  _$i$ from $1$ to $length(L)$_ do

4 Let $S$ be the set of columns contained in the first $i$ entries of list
$L$;

5 Let $H_{m,k-|S|}=(P_{m}\textnormal{ or }C_{m})\square P_{k-|S|}$;

6 Set $R^{\prime}=\left\\{v\in R:v\in H_{m,k-|S|}\right\\}$;

7 if $HasBroadcast(H_{m,k-|S|},R^{\prime},x-m_{i})$ then return True;

8

9 end for

10return False;

Algorithm 1 Routine to determine if assumed sub-broadcast implies bound.

######  Lemma 3.1.

Let $k\geq 13$, $B(n)$ be a lower bound of $\gamma_{b,2}(G_{m,n})$ for all
$n<n_{0}$ for some $n_{0}\geq k+3$, and let $g$ be a broadcast of cost $x$
whose broadcast range $R$ is contained in some $k$-column induced subgraph
$H_{m,k}$ of $G_{m,n_{0}}$. If $g$ is a sub-broadcast of an optimal broadcast
on $G_{m,n_{0}}$ and $InductiveArgument(H_{m,k},R,x,m_{1},m_{2},\dots,m_{k})$
is true, then $B(n_{0})\leq\gamma_{b,2}(G_{m,n_{0}})$. Here $m_{i}$ (for each
$i=1$ to $k$) is defined as in Section 3.4.

###### Proof.

Assume the conditions of Lemma 3.1. Let $f$ be an optimal $2$-limited
dominating broadcast of $G_{m,n_{0}}$ which contains $g$ as an induced sub-
broadcast. Let $f^{\prime}=f\ominus g$ and let $S$, $H_{m,k-|S|}$, and
$R^{\prime}$ be defined as in Algorithm 1. Let $G_{m,n_{0}-|S|}$ be
constructed by removing the set of columns $S$ from $G_{m,n_{0}}$ which
resulted in $InductiveArgument$ returning true on line 7 and adding edges in
the natural way such that the resulting graph is isomorphic to
$\left(P_{m}\textnormal{ or }C_{m}\right)\square C_{n_{0}-|S|}$.

######  Observation 3.

As $n_{0}\geq k+3$ and $\lvert S\rvert\leq k$, we have that $n_{0}-\lvert
S\rvert\geq 3$. Thus, $G_{m,n_{0}-\lvert S\rvert}$ is well-defined.

Let $f^{\prime\prime}$ be the broadcast formed by restricting $f^{\prime}$ to
$G_{m,n_{0}-|S|}$. That is, let $f^{\prime\prime}(v)=f^{\prime}(v)$ for all
$v\in V(G_{m,n_{0}-|S|})$. For each vertex $v\in V(G_{m,n_{0}})\setminus
V(G_{m,n_{0}-|S|})$ (i.e. all vertices $v$ in the set of columns $S$)
broadcasting with non-zero strength under $f^{\prime}$, pick a vertex $u$ in
the same row as $v$ and in an undeleted column nearest to $v$ and let
$f^{\prime\prime}(u)=\textnormal{
max}\left\\{f^{\prime}(u),f^{\prime}(v)\right\\}$. Note that
$cost(f^{\prime\prime})\leq cost(f^{\prime})$.

######  Observation 4.

The broadcast $f^{\prime\prime}$ dominates $V(G_{m,n_{0}-|S|})$ with the
possible exception of the vertices of $R^{\prime}$.

###### Proof.

Fix $v\in V(G_{m,n_{0}-|S|})\setminus R^{\prime}$. As $v\not\in R^{\prime}$,
$v$ is not dominated by $g$ on $G_{m,n_{0}}$. There are two cases:

Case 1, $v$ hears a broadcast from a vertex $u$ under $f^{\prime}$ and $u$ is
not in the set of columns $S$. As $f^{\prime\prime}(u)\geq f^{\prime}(u)$,
since $v$ hears a broadcast from $u$ under $f^{\prime}$ on $G_{m,n_{0}}$, $v$
hears a broadcast from $u$ under $f^{\prime\prime}$ on $G_{m,n_{0}-|S|}$.

Case 2, $v$ hears a broadcast from a vertex $u$ under $f^{\prime}$ and $u$ is
in the set of columns $S$. As $u\not\in V(G_{m,n_{0}-|S|})$, there exists a
vertex $u^{\prime}\in V(G_{m,n_{0}-|S|})$ in the same row as $u$ and in a
nearest column undeleted to $u$ such that $f^{\prime\prime}(u^{\prime})\geq
f^{\prime}(u)$. Note that, by Observation 3, such a vertex exists. It suffices
to check that $v$ hears a broadcast from $u^{\prime}$ under $f^{\prime\prime}$
on $G_{m,n_{0}-|S|}$. Since $f^{\prime}(u)\leq 2$ and
$G_{m,n_{0}}=(P_{m}\textnormal{ or }C_{m})\square C_{n_{0}}$, there are two
subcases:

Subcase 2.a), $u^{\prime}$ is on the same column as $v$ or $u^{\prime}$ is on
the column between $v$ and $u$ on $G_{m,n_{0}}$. Since $u^{\prime}$ is in the
same row as $u$, $d(u^{\prime},v)\leq d(u,v)$ in $G_{m,n_{0}}$. As
$f^{\prime\prime}(u^{\prime})\geq f^{\prime}(u)$, since $v$ hears a broadcast
from $u$ under $f^{\prime}$ on $G_{m,n_{0}}$, $v$ hears a broadcast from
$u^{\prime}$ under $f^{\prime\prime}$ on $G_{m,n_{0}-|S|}$.

Subcase 2.b), $u$ is on a column between $v$ and $u^{\prime}$ on
$G_{m,n_{0}}$. As $u^{\prime}$ is on a nearest column to $u$ that is
undeleted, the column of $u^{\prime}$ on $G_{m,n_{0}-|S|}$ is at distance at
most $d_{G_{m,n_{0}}}(u,v)$ (the distance between $u$ and $v$ in
$G_{m,n_{0}}$) from the column containing $v$. As $u^{\prime}$ is in the same
row as $u$ and $f^{\prime\prime}(u^{\prime})\geq f^{\prime}(u)$, since $v$
hears a broadcast from $u$ under $f^{\prime}$ on $G_{m,n_{0}}$, $v$ hears a
broadcast from $u^{\prime}$ under $f^{\prime\prime}$ on $G_{m,n_{0}-|S|}$. ∎

By Observation 4, to dominate $G_{m,n_{0}-|S|}$, it suffices to find a
$2$-limited broadcast which dominates $R^{\prime}$. As the function call on
line 7 returns true, $R^{\prime}$ can be dominated by a $2$-limited broadcast
$h$ with cost less than or equal to $x-m_{|S|}$ where $x=cost(g)$. Note that,
for this to be true, $m_{|S|}\neq\infty$. Let
$f^{\prime\prime\prime}=f^{\prime\prime}\oplus h$. The broadcast
$f^{\prime\prime\prime}$ is a $2$-limited dominating broadcast on
$G_{m,n_{0}-|S|}$. By the inductive assumption,

$B(n_{0}-|S|)\leq\gamma_{b,2}(G_{m,n_{0}-|S|})\leq
cost(f^{\prime\prime\prime}).$ (2)

Observe that

$\displaystyle cost(f^{\prime\prime\prime})=cost(f^{\prime\prime}\oplus
h)=cost(f^{\prime\prime})+cost(h)$ $\displaystyle\leq
cost(f^{\prime})+cost(h)$ (3) $\displaystyle\leq cost(f^{\prime})+x-m_{|S|}$
$\displaystyle=cost(f\ominus g)+x-m_{|S|}$
$\displaystyle=cost(f)-cost(g)+x-m_{|S|}$ $\displaystyle=cost(f)-m_{|S|}.$

As $m_{|S|}\geq B(n_{0})-B(n_{0}-|S|)$, when combined with Equations 2 and 3,
we have that

$\displaystyle B(n_{0})\leq B(n_{0}-|S|)+m_{|S|}\leq
cost(f^{\prime\prime\prime})+m_{|S|}\leq cost(f)=\gamma_{b,2}(G_{m,n_{0}})$

as desired.

∎

######  Example 3.2.

Suppose we wish to establish $n\leq\gamma_{b,2}(P_{5}\square C_{n})$; doing so
will yield periodically optimal values for $\gamma_{b,2}(P_{5}\square C_{n})$.
By computation, we have that $n\leq\gamma_{b,2}\left(P_{5}\square
C_{n}\right)$ for $3\leq n\leq 16$. Suppose the bound holds for all $n<n_{0}$
where $n_{0}>16$. Let $f$ be an optimal $2$-limited dominating broadcast of
$P_{5}\square C_{n_{0}}$ and let $C$ be the subgraph of $P_{5}\square
C_{n_{0}}$ induced by the vertices appearing in a minimum cost set of eight
consecutive columns with respect to $f$. Suppose $V(C)$ induces the sub-
broadcast $g$ shown in Figure 3.

Figure 3: Assumed sub-broadcast $g$ induced by $V(C)$ of cost 7.

Let $f^{\prime}=f\ominus g$ and let $R$ be the range of $g$. The broadcast
$f^{\prime}$ dominates $V(P_{5}\square C_{n_{0}})$ with the possible exception
of the vertices of $R$. Suppose we delete the four columns indicated in Figure
4 (Left) from the grid and add edges in the natural way such that the
resulting graph $G_{5,n_{0}-4}=P_{5}\square C_{n_{0}-4}$.

columns to be deleted

$\rightarrow$ resulting region after deletion

Figure 4: (Left & Middle) Procedure which reduces $G_{m,n_{0}}$ to
$G_{m,n_{0}-4}$. (Right) Broadcast of cost 3 which dominates $R^{\prime}$.

Let $f^{\prime\prime}$ be the broadcast formed by restricting $f^{\prime}$ to
$G_{m,n_{0}-4}$. That is, let $f^{\prime\prime}(v)=f^{\prime}(v)$ for all
$v\in V(G_{m,n_{0}-4})$. Let $R^{\prime}=\left\\{v\in V(G_{m,n_{0}-4}):v\in
R\right\\}$. The vertices of $R^{\prime}$ are indicated by the green circles
in Figures 4 (Middle). The broadcast $f^{\prime\prime}$ dominates
$V(G_{m,n_{0}-4})$ with the possible exception of the vertices of
$R^{\prime}$. However, $R^{\prime}$ can be dominated by the broadcast $h$ of
cost 3 as shown in Figure 4 (Right). Let
$f^{\prime\prime\prime}=f^{\prime\prime}\oplus h$. The broadcast
$f^{\prime\prime\prime}$ is a $2$-limited dominating broadcast on
$G_{5,n_{0}-4}=P_{5}\square C_{n_{0}-4}$. By assumption,
$n_{0}-4\leq\gamma_{b,2}(P_{5}\square C_{n_{0}-4})\leq
cost(f^{\prime\prime\prime})$. As

$\displaystyle cost(f^{\prime\prime\prime})\leq
cost(f^{\prime\prime})+3=cost(f\ominus g)+3\leq cost(f)-4,$

we conclude that $n_{0}\leq cost(f)=\gamma_{b,2}(P_{5}\square C_{n_{0}})$ as
desired.

###  3.5 Necessary Broadcasts

Given some possible sub-broadcast $g$, the broadcast structure of $g$ may
imply the existence of a larger sub-broadcast $g^{\prime}$. If this broadcast
$g^{\prime}$ does not pass the optimality requirement (see Section 3.3), then
$g$ can be eliminated. If this broadcast $g^{\prime}$ allows for the induction
argument (see Section 3.4), then $g$ implies the bound we hope to prove.

######  Observation 5.

As $g$ is induced by $V(C)$, for each vertex in column $c_{6}$ or $c_{k-5}$
not dominated by $g$, any dominating broadcast of $G_{m,n_{0}}$ must have a
vertex broadcasting at strength 2, in the same row and in column $c_{4}$ or
$c_{k-3}$.

See Figure 5 (Left). Let $g^{\prime}$ be the broadcast constructed from $g$ by
adding these necessary broadcasts. Let $R^{\prime}$ be the range of
$g^{\prime}$. Let $NecessaryBroadcast(H_{m,k},$ $g,$ $m_{1},$ $m_{2},$
$\dots,$ $m_{k})$ return true if either $HasBroadcast(H_{m,k},$ $R^{\prime},$
$cost(g^{\prime})-1)$ or $InductiveArgument(H_{m,k},$ $R^{\prime},$
$cost(g^{\prime}),$ $m_{1},$ $m_{2},$ $\dots,$ $m_{k})$ returns true and false
otherwise.

$c_{2}$$c_{4}$$c_{6}$$c_{1}$$c_{3}$$c_{5}$$c_{7}$$c_{k-6}$$c_{k-4}$$c_{k-2}$$c_{k}$$c_{k-5}$$c_{k-3}$$c_{k-1}$$\dots$$\dots$$\vdots$$\vdots$

$c_{2}$$c_{4}$$c_{6}$$c_{1}$$c_{3}$$c_{5}$$c_{7}$$c_{k-6}$$c_{k-4}$$c_{k-2}$$c_{k}$$c_{k-5}$$c_{k-3}$$c_{k-1}$$\dots$$\dots$$\vdots$$\vdots$

Figure 5: The graph $H_{m,k}$ with columns labelled $c_{1},c_{2},\dots,c_{k}$
and $C$ indicated by the thick black rectangle. (Left) Resulting necessary
broadcasts of strength 2 in columns $c_{4}$ and $c_{k-3}$ forced by vertices
undominated in columns $c_{6}$ and $c_{k-5}$. (Right) Necessary broadcast
$g^{\prime}$ as described in Section 3.5, the vertex undominated by
$g^{\prime}$ indicated by the green circle, and one of the five possible sub-
broadcasts $g^{\prime\prime}$ which extend $g^{\prime}$ to dominate the vertex
undominated by $g^{\prime}$ in column $c_{k-4}$.

###  3.6 Considering All Possible Sub-Cases

When considering all possible sub-broadcasts $g$ and the necessary sub-
broadcasts $g^{\prime}$ they imply (see Section 3.5), some sub-broadcasts may
require that we consider all possible induced sub-broadcasts
$g^{\prime\prime}$ which extend $g^{\prime}$ to dominate $V(C)$.

Let $g^{\prime}$ be the necessary broadcast implied by $g$ as described in
Section 3.5. Note $g^{\prime}$ dominates $V(C)$ with the possible exception of
vertices in columns $c_{5}$ and $c_{k-4}$. There are many possible ways a
dominating $2$-limited broadcast could dominate the vertices in columns
$c_{5}$ and $c_{k-4}$ undominated by $g^{\prime}$. Let $\mathcal{C}^{\prime}$
be the collection of broadcasts formed by extending $g^{\prime}$ to include
vertices from $V(G_{m,k})\setminus\left[V(c_{5})\cup V(c_{6})\cup\dots\cup
V(c_{k-4})\right]$ broadcasting at strength 0, 1, or strength 2 until every
vertex in columns $c_{5}$ and $c_{k-4}$ which do not hear a broadcast under
$g^{\prime}$ is dominated. See Figure 5 (Right). Let $AllSubcases(H_{m,k},$
$g,$ $m_{1},$ $m_{2},$ $\dots,$ $m_{k})$ return true if either
$HasBroadcast(H_{m,k},$ $R^{\prime},$ $cost(g^{\prime})-1)$ or
$InductiveArgument(H_{m,k},$ $R^{\prime\prime},$ $cost(g^{\prime\prime}),$
$m_{1},$ $m_{2},$ $\dots,$ $m_{k})$ returns true for every
$g^{\prime\prime}\in\mathcal{C^{\prime}}$ and false otherwise.

Without loss of generality, we may assume that for each broadcast
$g^{\prime\prime}\in\mathcal{C}^{\prime}$,
$ForbiddenBroadcast(G_{m,k},g^{\prime\prime})$ is false. Additionally, for
each $g^{\prime\prime}\in\mathcal{C}^{\prime}$, if the vertices $u$ and $v$
are added to the broadcast to dominate a vertex in column $c_{5}$, we may
assume that the set of vertices dominated in column $c_{5}$ by $u$ is not a
subset of the set of vertices in column $c_{5}$ dominated by $v$, else $u$ is
redundant in terms of dominating the vertices of column $c_{5}$. The same
argument applies to the vertices dominating the vertices in column $c_{k-4}$.

###  3.7 Algorithm to Prove Lower Bounds

Algorithm 2: ProvedLowerBound implements the battery of tests described in
Section 3.1 through 3.6 to prove lower bounds for $C_{m}\square C_{n}$ and
$P_{m}\square C_{n}$. The correctness of Algorithm 2 is proven by Theorem 3.3.

1 function ProvedLowerBound $(H_{m,k},s,t,m_{1},m_{2},\dots,m_{k})$;

Input : A graph $H_{m,k}=(P_{m}\textnormal{ or }C_{m})\square P_{k}$, where
$k\geq 13$, with columns labelled from left to right by
$c_{1},c_{2},\dots,c_{k}$, the minimum $s$ and maximum $t$ possible costs of a
sub-broadcast $g$ of $H_{m,k}$ induced by columns $c_{5},c_{6},\dots,c_{k-4}$,
and $m_{i}$ (for each $i=1$ to $k$) as defined in Section 3.4.

Output : Value of the truth statement: “lower bound proven.”

2 Let $\mathcal{C}$ be all possible sub-broadcasts $g$ of costs $s$ to $t$
induced by the vertices of columns $c_{5},c_{6},\dots,c_{k-4}$;

3 foreach  _$g\in\mathcal{C}$_ do

4 if $DoesNotDominate(H_{m,k},g)$ then goto line 12;

5 if $ForbiddenBroadcast(H_{m,k},g)$ then goto line 12;

6 Let $R$ be the broadcast range of $g$;

7 if $HasBroadcast(H_{m,k},R,cost(g)-1)$ then goto line 12;

8 if $InductiveArgument(H_{m,k},R,cost(g),m_{1},m_{2},\dots,m_{k})$ then goto
line 12;

9 if $NecessaryBroadcast(H_{m,k},g,m_{1},m_{2},\dots,m_{k})$ then goto line
12;

10 if $AllSubcases(H_{m,k},g,m_{1},m_{2},\dots,m_{k})$ then goto line 12;

11 return False;

12

13 end foreach

14return True;

Algorithm 2 Routine to prove lower bound.

######  Theorem 3.3.

Let $k\geq 13$ and $B(n)$ be a lower bound of $\gamma_{b,2}(G_{m,n})$ for all
$n<n_{0}$ for some $n_{0}\geq k+3$. Let $s=\gamma_{b,2}(H_{m,k-12})$ and
$t=max\left\\{\ell:\exists n\geq n_{0}\textnormal{ s.t.
}\frac{n\ell}{k-8}<B(n)\right\\}$. If $ProvedLowerBound(H_{m,k},$ $s,$ $t,$
$m_{1},$ $m_{2},$ $\dots,$ $m_{k})$ is true, then
$B(n)\leq\gamma_{b,2}(G_{m,n})$ for all $n$. Here $m_{i}$ (for each $i=1$ to
$k$) is defined as in Section 3.4.

###### Proof.

Assume the conditions of Theorem 3.3 and suppose
$ProvedLowerBound(H_{m,k},s,t,m_{1},m_{2},\dots,m_{k})$ is true. Let $f$ be an
optimal $2$-limited dominating broadcast of $G_{m,n_{0}}$. Let $C$ be the
subgraph of $G_{m,n_{0}}$ induced by the vertices appearing in a minimum cost
set (with respect to $f$) of $r=k-8$ consecutive columns of $G_{m,n_{0}}$. Let
$H_{m,k}$ be the subgraph of $G_{m,n_{0}}$ centred on $C$ with columns
labelled $c_{1},c_{2},\dots,c_{k}$ and let $C^{\prime}$ be the subgraph of
$H_{m,k}$ induced by columns $c_{7},c_{8},\dots,c_{k-6}$. Note the vertices of
$C$ are in columns $c_{5},c_{6},\dots,c_{k-4}$ of $H_{m,k}$ and
$C^{\prime}=H_{m,k-12}$. The sub-broadcast $g$ of $f$ induced by $V(C)$ must
dominate $C^{\prime}$ (Observation 1). As $s=\gamma_{b,2}(C^{\prime})$, we
have that $cost(g)\geq s$. By our choice of $C$,

$\displaystyle cost(f)\geq\frac{n\cdot cost(g)}{r}=\frac{n\cdot
cost(g)}{k-8}.$

Thus, if $cost(g)>t$ then, by the definition of $t$, $cost(f)\geq B(n)$ for
all $n\geq n_{0}$. As $\mathcal{C}$ defined on line 2 is the set of all
possible sub-broadcasts of cost between $s$ and $t$, inclusive, induced by the
vertices of columns $c_{5},c_{6},\dots,c_{k-4}$, $g\in\mathcal{C}$. As
$ProvedLowerBound$ returned true, one of the function calls on lines 4 through
10 returned true for $g$. From the results in Sections 3.1 through 3.6, this
proves the claim. ∎

##  4 Results

Our implementation includes a canonicity test for $P_{m}\square P_{n}$ so as
to only consider the set $\mathcal{C}$ of all possible sub-broadcasts induced
by the vertices of some set of $r$ consecutive columns with costs between $s$
and $t$, inclusive, up to isomorphism. That is, for each pair of broadcasts
$g,g^{*}\in\mathcal{C}$, there is no group action on $P_{m}\square P_{n}$
which defines an automorphism between $g$ and $g^{*}$. This test was done by
checking that each broadcast (when expressed as a sequence) was the maximum
lexicographically when compared to all broadcasts isomorphic to it. When
adapting the code to work on $C_{m}\square C_{n}$, we did not update the
canonicity test to reduce the number of cases up to isomorphism on
$C_{m}\square P_{n}$ from $P_{m}\square P_{n}$. Fortunately, this redundancy
was acceptable in terms of run time. The number of induced sub-broadcasts
(i.e. $\lvert\mathcal{C}\rvert$) have been verified by Pólya’s Theorem (see
[2, Theorem 14.3.3]).

Our implementation of $ProvedLowerBound$ has allowed us to prove Theorems 4.1
through 4.11, and their respective corollaries. For each theorem, we include a
table which summarizes the number of broadcasts rejected at each step of the
algorithm per considered cost. Steps with zero cases are omitted.
Additionally, as $AllSubcases$ considers all possible induced sub-broadcasts
of a given case, the total number of cases considered will be at least
$\left|\mathcal{C}\right|$.

Our implementation is written in C++ and available here [15]. All ILP calls
are run with a Gurobi solver [9]. All computations in this section were run on
Slobodin’s 2021 16GB MacBook Pro with an Apple M1 Pro processor.

######  Theorem 4.1.

For $n\geq 3$, $\gamma_{b,2}\left(C_{3}\square
C_{n}\right)=\left\lceil\frac{2n}{3}\right\rceil$.

###### Proof.

Theorem 6 of [16] proves that $\gamma_{b,2}\left(C_{3}\square
C_{n}\right)\leq\left\lceil 2n/3\right\rceil$. Fix $r=6$ and let $k=14=r+8$.
By computation, we know that the upper bound is optimal for all $3\leq n\leq
16=k+2$. Given the upper bound, for $1\leq i\leq 14=k$, $m_{i}$ is defined as
follows:

$\displaystyle(m_{1},m_{2},\dots,m_{14})=(1,2,2,3,4,4,5,6,6,7,8,8,9,10).$

As $r-4=2$ and $\gamma_{b,2}\left(C_{3}\square P_{2}\right)=2$, set $s=2$. Set
$t=3$. Observe that, for $n=17$,

$\displaystyle\left\lceil\frac{3n}{6}\right\rceil=9<11=\left\lceil\frac{2n}{3}\right\rceil=B(n),$

thus $t\geq 3$. If $t>3$, then there exists an $n>16$ such that

$\displaystyle\left\lceil\frac{4n}{6}\right\rceil\leq\frac{tn}{6}<B(n)=\left\lceil\frac{4n}{6}\right\rceil,$

which is a contradiction. As $ProvedLowerBound\left(C_{3}\square
P_{14},2,3,m_{1},m_{2},\dots,m_{14}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took under one second.

| Cost 2 | Cost 3
---|---|---
$\left|\mathcal{C}\right|$ | 54 | 302
$DoesNotDominate$ | 48 | 231
$ForbiddenBroadcast$ | 4 | 45
$InductiveArgument$ | 0 | 12
$NecessaryBroadcast+HasBroadcast$ | 0 | 8
$NecessaryBroadcast+InductiveArgument$ | 2 | 3
$AllSubcases+HasBroadcast$ | 0 | 45
$AllSubcases+InductiveArgument$ | 0 | 63
Table 1: Cases considered in the proof of Theorem 4.1.

######  Corollary 4.2.

For $m\geq 3$, $\gamma_{b,2}\left(P_{m}\square
C_{3}\right)=\left\lceil\frac{2m}{3}\right\rceil$.

###### Proof.

The bound is easily verified by computation for $3\leq m\leq 22$. Theorem 5 of
[16] proves that $\gamma_{b,2}\left(P_{m}\square C_{3}\right)\leq\left\lceil
2n/3\right\rceil$ for all $m\geq 23$. As any $2$-limited dominating broadcast
on $P_{m}\square C_{3}$ is a $2$-limited dominating broadcast on $C_{m}\square
C_{3}$, $\gamma_{b,2}\left(C_{3}\square
C_{m}\right)\leq\gamma_{b,2}\left(P_{m}\square C_{3}\right)$. The result
follows from Theorem 4.1. ∎

######  Theorem 4.3.

For $n\geq 4$, $\gamma_{b,2}\left(C_{4}\square
C_{n}\right)=4\left\lfloor\frac{n}{6}\right\rfloor+\begin{cases}0&\textnormal{for
}n\equiv 0\pmod{6},\\\ 2&\textnormal{for }n\equiv 1\textnormal{ or
}2\pmod{6},\\\ 3&\textnormal{for }n\equiv 3\textnormal{ or
}4\pmod{6},\textnormal{ and}\\\ 4&\textnormal{for }n\equiv 5\pmod{6}.\\\
\end{cases}$

###### Proof.

Theorem 6 of [16] proves that $\gamma_{b,2}\left(C_{4}\square C_{n}\right)$ is
less than or equal to the stated value. Fix $r=6$ and let $k=14=r+8$. By
computation, we know that the stated value is optimal for all $3\leq n\leq
16=k+2$. Given the upper bound, for $1\leq i\leq 14=k$, $m_{i}$ is defined as
follows:

$\displaystyle(m_{1},m_{2},\dots,m_{14})=(2,2,3,3,4,4,6,6,7,7,8,8,10,10).$

As $r-4=2$ and $\gamma_{b,2}\left(C_{4}\square P_{2}\right)=2$, set $s=2$. Let
$n_{6}$ be the least residue of $n$ modulo $6$ and let $c(n_{6})$ be the
constant in the upper bound dependent upon $n_{6}$. Set $t=4$. Observe that,
for $n=19$,

$\displaystyle\left\lceil\frac{4n}{6}\right\rceil=13<14=4\left\lfloor\frac{n}{6}\right\rfloor+2=4\left\lfloor\frac{n}{6}\right\rfloor+n_{6}=B(n),$

thus $t\geq 4$. If $t>4$, then there exists an $n>16$ such that

$\displaystyle\frac{5n}{6}\leq\frac{tn}{6}<B(n)=4\left\lfloor\frac{n}{6}\right\rfloor+c(n_{6})=\frac{4n}{6}-\frac{4n_{6}}{6}+c(n_{6})\leq\frac{4n}{6}+\frac{4}{3}\Rightarrow
n<8,$

which is a contradiction. As $ProvedLowerBound\left(C_{4}\square
P_{14},2,4,m_{1},m_{2},\dots,m_{14}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took less than one second.

| Cost 2 | Cost 3 | Cost 4
---|---|---|---
$\left|\mathcal{C}\right|$ | 84 | 644 | 4,302
$DoesNotDominate$ | 83 | 610 | 3,770
$ForbiddenBroadcast$ | 0 | 16 | 378
$InductiveArgument$ | 0 | 0 | 98
$NecessaryBroadcast+HasBroadcast$ | 1 | 16 | 33
$NecessaryBroadcast+InductiveArgument$ | 0 | 2 | 20
$AllSubcases+HasBroadcast$ | 0 | 0 | 2
$AllSubcases+InductiveArgument$ | 0 | 0 | 30
Table 2: Cases considered in the proof of Theorem 4.3.

######  Corollary 4.4.

For $m\geq 3$, $\gamma_{b,2}\left(P_{m}\square
C_{4}\right)=4\left\lfloor\frac{m}{6}\right\rfloor+\begin{cases}0\textnormal{
or }1&\textnormal{for }m\equiv 0\pmod{6},\\\ 2&\textnormal{for }m\equiv
1\textnormal{ or }2\pmod{6},\\\ 3&\textnormal{for }m\equiv 3\pmod{6},\\\
3\textnormal{ or }4&\textnormal{for }m\equiv 4\pmod{6},\textnormal{ and}\\\
4&\textnormal{for }m\equiv 5\pmod{6}.\\\ \end{cases}$

###### Proof.

The bound is easily verified by computation for $3\leq m\leq 22$. Theorem 5 of
[16] proves that $\gamma_{b,2}\left(P_{m}\square C_{4}\right)$ is less than or
equal to the bound in the corollary statement for $m\geq 23$. As any
$2$-limited dominating broadcast on $P_{m}\square C_{4}$ is a $2$-limited
dominating broadcast on $C_{m}\square C_{4}$, $\gamma_{b,2}\left(C_{4}\square
C_{m}\right)\leq\gamma_{b,2}\left(P_{m}\square C_{4}\right)$. The result
follows from Theorem 4.3. ∎

######  Theorem 4.5.

For $n\geq 5$, $\gamma_{b,2}\left(C_{5}\square C_{n}\right)=n$.

###### Proof.

Theorem 6 of [16] proves that $\gamma_{b,2}\left(C_{5}\square C_{n}\right)\leq
n$. Fix $r=8$ and let $k=16=r+8$. By computation, we know that the upper bound
is optimal for all $3\leq n\leq 18=k+2$. Given the upper bound, for $1\leq
i\leq 16=k$, $m_{i}$ is defined as follows:

$\displaystyle(m_{1},m_{2},\dots,m_{16})=(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16).$

As $r-4=4$ and $\gamma_{b,2}\left(C_{5}\square P_{4}\right)=5$, set $s=5$. Set
$t=7$. Observe that, for $n=19$,

$\displaystyle\left\lceil\frac{7n}{8}\right\rceil=17<19=n=B(n),$

thus $t\geq 7$. If $t>7$, then there exists an $n>18$ such that

$\displaystyle\frac{8n}{8}\leq\frac{tn}{8}<B(n)=n,$

which is a contradiction. As $ProvedLowerBound\left(C_{5}\square
P_{16},5,7,m_{1},m_{2},\dots,m_{16}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took less than one minute.

| Cost 5 | Cost 6 | Cost 7
---|---|---|---
$\left|\mathcal{C}\right|$ | 264,148 | 1,925,104 | 12,162,548
$DoesNotDominate$ | 264,115 | 1,922,880 | 12,103,722
$ForbiddenBroadcast$ | 8 | 1,423 | 48,899
$HasBroadcast$ | 0 | 161 | 5,198
$InductiveArgument$ | 25 | 632 | 4,696
$NecessaryBroadcast$ | 0 | 5 | 27
$+InductiveArgument$
$AllSubcases+HasBroadcast$ | 0 | 27 | 0
$AllSubcases$ | 0 | 48 | 30
$+InductiveArgument$
Table 3: Cases considered in the proof of Theorem 4.5.

######  Corollary 4.6.

For $m\geq 3$, $m\leq\gamma_{b,2}\left(P_{m}\square C_{5}\right)\leq m+1$.

###### Proof.

Theorem 5 of [16] proves that $\gamma_{b,2}(P_{m}\square C_{5})\leq m+1$. The
lower bound is easily verified by computation for $3\leq m\leq 4$. As any
$2$-limited dominating broadcast on $P_{m}\square C_{5}$ is a $2$-limited
dominating broadcast on $C_{m}\square C_{5}$, $\gamma_{b,2}\left(C_{5}\square
C_{m}\right)\leq\gamma_{b,2}\left(P_{m}\square C_{5}\right)$. The result
follows from Theorem 4.5. ∎

######  Theorem 4.7.

For $n\geq 6$, $\gamma_{b,2}\left(C_{6}\square
C_{n}\right)=n+\begin{cases}0&\textnormal{for }n\equiv 0\pmod{4}\textnormal{
and}\\\ 1&\textnormal{for }n\equiv 1,2,\textnormal{ or }3\pmod{4}.\\\
\end{cases}$

###### Proof.

Theorem 6 of [16] proves that $\gamma_{b,2}\left(C_{6}\square C_{n}\right)$ is
less than or equal to the stated value. Fix $r=8$ and let $k=16=r+8$. By
computation, we know that the stated value is optimal for all $3\leq n\leq
18=k+2$. Given the upper bound, for $1\leq i\leq 16=k$, $m_{i}$ is defined as
follows:

$\displaystyle(m_{1},m_{2},\dots,m_{16})=(2,3,4,4,6,7,8,8,10,11,12,12,14,15,16,16).$

As $r-4=4$ and $\gamma_{b,2}\left(C_{6}\square P_{4}\right)=5$, set $s=5$. Let
$n_{4}$ be the least residue of $n$ modulo $4$ and let $c(n_{4})$ be the
constant in the upper bound dependent upon $n_{4}$. Set $t=8$. Observe that,
for $n=19$,

$\displaystyle\left\lceil\frac{8n}{8}\right\rceil=19<20=n+1=n+c(n_{4})=B(n),$

thus $t\geq 8$. If $t>8$, then there exists an $n>18$ such that

$\displaystyle\frac{9n}{8}\leq\frac{tn}{8}<B(n)=n+c(n_{4})\leq n+1\Rightarrow
n<8$

which is a contradiction. As $ProvedLowerBound\left(C_{6}\square
P_{16},5,8,m_{1},m_{2},\dots,m_{16}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took less than seven minutes.

| Cost 5 | Cost 6 | Cost 7 | Cost 8
---|---|---|---|---
$\left|\mathcal{C}\right|$ | 635,628 | 5,506,384 | 41,289,876 | 273,548,430
$DoesNotDominate$ | 635,625 | 5,506,080 | 41,277,225 | 273,227,125
$ForbiddenBroadcast$ | 0 | 138 | 9,204 | 278,760
$HasBroadcast$ | 0 | 21 | 1,368 | 31,477
$InductiveArgument$ | 0 | 67 | 1,698 | 10,361
$NecessaryBroadcast$ | 3 | 78 | 330 | 563
$+$ $HasBroadcast$
$NecessaryBroadcast$ | 0 | 0 | 39 | 102
$+InductiveArgument$
$AllSubcases$ | 0 | 0 | 1,262 | 5914
$+HasBroadcast$
$AllSubcases$ | 0 | 0 | 78 | 204
$+InductiveArgument$
Table 4: Cases considered in the proof of Theorem 4.7.

######  Corollary 4.8.

For $m\geq 3$, $\gamma_{b,2}\left(P_{m}\square
C_{6}\right)=m+\begin{cases}0\textnormal{ or }1&\textnormal{for }m\equiv
0\pmod{4}\textnormal{ and}\\\ 1&\textnormal{for }m\equiv 1,2,\textnormal{ or
}3\pmod{4}.\\\ \end{cases}$

###### Proof.

Theorem 5 of [16] proves that $\gamma_{b,2}(P_{m}\square C_{6})\leq m+1$. The
lower bound is easily verified by computation for $3\leq m\leq 5$. As any
$2$-limited dominating broadcast on $P_{m}\square C_{6}$ is a $2$-limited
dominating broadcast on $C_{m}\square C_{6}$, $\gamma_{b,2}\left(C_{6}\square
C_{m}\right)\leq\gamma_{b,2}\left(P_{m}\square C_{6}\right)$. The result
follows from Theorem 4.7. ∎

######  Theorem 4.9.

For $n\geq 3$, $\gamma_{b,2}\left(P_{4}\square
C_{n}\right)=8\left\lfloor\frac{n}{10}\right\rfloor+c(n_{10})$ where
$c(n_{10})$ is dependent upon the least residue $n_{10}$ of $n$ modulo $10$
and given in Table 5.

|  Least residue $n_{10}$ of $n$ modulo $10$
---|---
$n_{10}$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$
$c(n_{10})$: | $0$ | $2$ | $2$ | $3$ | $4$ | $5$ | $5$ | $6$ | $7$ | $8$
Table 5: Values of $c(n_{10})$ for $\gamma_{b,2}\left(P_{4}\square
C_{n}\right)$ stated in Theorem 4.9.

###### Proof.

Theorem 3 of [16] proves that $\gamma_{b,2}\left(P_{4}\square C_{n}\right)$ is
less than or equal to the stated value. Fix $r=10$ and let $k=18=r+8$. By
computation, we know that the stated value is optimal for all $3\leq n\leq
20=k+2$. Given the upper bound, for $1\leq i\leq 18=k$, $m_{i}$ is defined as
follows:

$\displaystyle(m_{1},m_{2},\dots,m_{18})=(2,2,3,4,5,5,6,7,8,8,10,10,11,12,13,13,14,15).$

As $r-4=6$ and $\gamma_{b,2}\left(P_{4}\square P_{6}\right)=6$, set $s=6$. Let
$n_{10}$ be the least residue of $n$ modulo $10$ and let $c(n_{10})$ be the
constant in the upper bound dependent upon $n_{10}$. Set $t=8$. Observe that,
for $n=21$,

$\displaystyle\left\lceil\frac{8n}{10}\right\rceil=17<18=8\left\lfloor\frac{n}{10}\right\rfloor+2=8\left\lfloor\frac{n}{10}\right\rfloor+c(n_{10})=B(n),$

thus $t\geq 8$. If $t>8$, then there exists an $n>20$ such that

$\displaystyle\frac{9n}{10}\leq\frac{tn}{10}<B(n)=8\left\lfloor\frac{n}{10}\right\rfloor+c(n_{10})=\frac{8n}{10}-\frac{8n_{10}}{10}+c(n_{10})\leq\frac{8n}{10}+\frac{12}{10}\Rightarrow
n<12,$

which is a contradiction. As $ProvedLowerBound\left(P_{4}\square
P_{18},6,8,m_{1},m_{2},\dots,m_{18}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took less than 30 seconds.

| Cost 6 | Cost 7 | Cost 8
---|---|---|---
$\left|\mathcal{C}\right|$ | 1,922,800 | 12,154,870 | 67,920,535
$DoesNotDominate$ | 1,922,790 | 12,153,957 | 67,886,561
$ForbiddenBroadcast$ | 1 | 546 | 27,525
$HasBroadcast$ | 0 | 136 | 4,944
$InductiveArgument$ | 7 | 215 | 1,472
$NecessaryBroadcast+HasBroadcast$ | 1 | 8 | 16
$NecessaryBroadcast$ | 0 | 6 | 12
$+InductiveArgument$
$AllSubcases+HasBroadcast$ | 3 | 8 | 61
$AllSubcases$ | 13 | 28 | 43
$+InductiveArgument$
Table 6: Cases considered in the proof of Theorem 4.9.

######  Corollary 4.10.

(a) For $n\geq 4$,
$8\left\lfloor\frac{n}{10}\right\rfloor+c(n_{10})\leq\gamma_{b,2}\left(P_{4}\square
P_{n}\right)$ where $c(n_{10})$ is dependent upon the least residue $n_{10}$
of $n$ modulo $10$ and given in Table 5. (b) The lower bound stated in (a)
gives optimal values for $\gamma_{b,2}(P_{4}\square P_{n})$ for all $n\equiv
1,4,5,\textnormal{ and }9\pmod{10}$

###### Proof.

(a) As any $2$-limited dominating broadcast on $P_{4}\square P_{n}$ is a
$2$-limited dominating broadcast on $P_{4}\square C_{n}$,
$\gamma_{b,2}\left(P_{4}\square C_{n}\right)\leq\gamma_{b,2}\left(P_{4}\square
P_{n}\right)$. The lower bound follows from Theorem 4.9. (b) Theorem 1 of [16]
proves that $\gamma_{b,2}\left(P_{4}\square P_{n}\right)\leq
8\left\lfloor\frac{n}{10}\right\rfloor+d(n_{10})$ where $d(n_{10})$ is
dependent upon the least residue $n_{10}$ of $n$ modulo $10$ and given in
Table 7. The result follows. ∎

| Least residue $n_{10}$ of $n$ modulo $10$
---|---
$n_{10}$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$
$d(n_{10})$ | $1$ | $2$ | $3$ | $4$ | $4$ | $5$ | $6$ | $7$ | $8$ | $8$
Table 7: Values of $d(n_{10})$ for $\gamma_{b,2}\left(P_{4}\square
P_{n}\right)$ stated in Theorem 3.1 of [16].

######  Theorem 4.11.

For $n\geq 3$, $\gamma_{b,2}\left(P_{5}\square
C_{n}\right)=n+\begin{cases}0&\textnormal{for }n\equiv 0\pmod{2}\textnormal{
and}\\\ 1&\textnormal{for }n\equiv 1\pmod{2}.\\\ \end{cases}$

###### Proof.

Theorem 3 of [16] proves that $\gamma_{b,2}\left(P_{5}\square C_{n}\right)$ is
less than or equal to stated value. Fix $r=11$ and let $k=19=r+8$. By
computation, we know that the stated value is optimal for all $3\leq n\leq
21=k+2$. Given the upper bound, for $1\leq i\leq 19=k$, $m_{i}$ is defined as
follows:

$\displaystyle(m_{1},m_{2},\dots,m_{19})=(2,2,4,4,6,6,8,8,10,10,12,12,14,14,16,16,18,18,20).$

As $r-4=7$ and $\gamma_{b,2}\left(P_{5}\square P_{7}\right)=8$, set $s=8$. Let
$n_{2}$ be the least residue of $n$ modulo $2$ and let $c(n_{2})$ be the
constant in the upper bound dependent upon $n_{2}$. Set $t=11$. Observe that,
for $n=23$,

$\displaystyle\left\lceil\frac{11n}{11}\right\rceil=23<24=n+1=n+c(n_{2})=B(n),$

thus $t\geq 11$. If $t>11$, then there exists an $n>21$ such that

$\displaystyle\frac{12n}{11}\leq\frac{tn}{11}<B(n)=n+c(n_{2})\leq
n+1\Rightarrow n<11,$

which is a contradiction. As $ProvedLowerBound\left(P_{5}\square
P_{19},8,11,m_{1},m_{2},\dots,m_{19}\right)$ is true, the result follows. ∎

Running ProvedLowerBound for the above values took less than 30 minutes.

| Cost 8 | Cost 9 | Cost 10 | Cost 11
---|---|---|---|---
$\left|\mathcal{C}\right|$ | 777,158,275 | 5,239,827,968 | 32,027,967,253 | 179,128,860,188
$DoesNotDominate$ | 777,158,269 | 5,239,826,944 | 32,027,887,652 | 179,125,748,233
$ForbiddenBroadcast$ | 0 | 514 | 61,253 | 2,782,915
$HasBroadcast$ | 0 | 213 | 14,112 | 311,874
$InductiveArgument$ | 5 | 287 | 4,208 | 17,127
$NecessaryBroadcast$ | 1 | 7 | 14 | 21
$+$ $HasBroadcast$
$NecessaryBroadcast$ | 0 | 3 | 12 | 14
$+InductiveArgument$
$AllSubcases$ | 0 | 0 | 1 | 25
$+HasBroadcast$
$AllSubcases$ | 0 | 0 | 15 | 26
$+InductiveArgument$
Table 8: Cases considered in the proof of Theorem 4.11.

######  Corollary 4.12.

For $n\geq 5$, $\gamma_{b,2}\left(P_{5}\square
P_{n}\right)=n+\begin{cases}0\textnormal{ or }1&\textnormal{for }n\equiv
0\pmod{2}\textnormal{ and}\\\ 1&\textnormal{for }n\equiv 1\pmod{2}.\\\
\end{cases}$

###### Proof.

Theorem 1 of [16] proves that $\gamma_{b,2}\left(P_{5}\square P_{n}\right)\leq
n+1$. As any $2$-limited dominating broadcast on $P_{5}\square P_{n}$ is a
$2$-limited dominating broadcast on $P_{5}\square C_{n}$,
$\gamma_{b,2}\left(P_{5}\square C_{n}\right)\leq\gamma_{b,2}\left(P_{5}\square
P_{n}\right)$. The result follows from Theorem 4.11. ∎

##  5 Future Work

This paper presents a method for computationally proving lower bounds for the
$2$-limited broadcast domination of the Cartesian product of two paths, a path
and a cycle, and two cycles. Exact values for the $2$-limited broadcast
domination number of $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$ have been found, as have 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 can likely be extended to other graphs and $k$-limited
broadcast domination for $k>2$. We note the follow rather natural questions.

######  Problem 5.1.

Can this method be optimized further to prove bounds on larger graphs or graph
other than the Cartesian product of two paths, a path and a cycle, and two
cycles?

######  Problem 5.2.

Can this method be altered to prove bounds for the $k$-limited broadcast
domination number on the Cartesian product of two paths, a path and a cycle,
and two cycles?

Note: Using the methods described in this paper, and an improved backtracking
technique, we have also proven, for $n\geq 8$,

$\gamma_{b,2}\left(C_{8}\square
C_{n}\right)=8\left\lfloor\frac{n}{6}\right\rfloor+\begin{cases}0&\textnormal{for
}n\equiv 0\pmod{6},\\\ 2&\textnormal{for }n\equiv 1\pmod{6},\\\
4&\textnormal{for }n\equiv 2\pmod{6},\\\ 6&\textnormal{for }n\equiv
3\textnormal{ or }4\pmod{6},\textnormal{ and}\\\ 8&\textnormal{for }n\equiv
5\pmod{6}.\\\ \end{cases}$

This computation took one year and considered over 223 trillion cases. For
each proof in this paper, we used a backtracking algorithm to construct the
set $\mathcal{C}$ of all possible sub-broadcasts. In our improved backtracking
algorithm, we forbid the addition of any ForbiddenBroadcast (see Section 3.2).
The number of cases produced by this improved backtrack cannot be verified by
Pólya’s Theorem (see [2, Theorem 14.3.3]). As such, these results will be
reported elsewhere with an updated methodology and justification.

### Acknowledgements

All computations for this paper we run on machines purchased by Myrvold using
NSERC funding. We would also like to thank the referees for their thoughtful
and instructive comments

## References

  * [1] B. Bresar and S. Spacapan.  Broadcast domination of products of graphs.  Ars Combinatoria, 92:303–320, 2009.
  * [2] R.A. Brualdi.  Introductory Combinatorics.  Pearson Prentice Hall, 5th edition, 2010.
  * [3] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas.  Dominating 2-broadcast in graphs: Complexity, bounds and extremal graphs.  Applicable Analysis and Discrete Mathematics, 12:205–223, 2018.
  * [4] J. Caceres, C. Hernando, M. Mora, I. M. Pelayo, and M. L. Puertas.  General bounds on limited broadcast domination.  Discrete Mathematics and Theoretical Computer Science, 20:13, 2018.
  * [5] E. J. Cockayne, S. Herke, and C. M. Mynhardt.  Broadcasts and domination in trees.  Discrete Mathematics, 311(13):1235–1246, 2011.  Selected Papers from the 22nd British Combinatorial Conference.
  * [6] J. E. Dunbar, D. J. Erwin, T. W. Haynes, S. M. Hedetniemi, and S. T. Hedetniemi.  Broadcasts in graphs.  Discrete Applied Mathematics, 154(1):59–75, 2006.
  * [7] D. J. Erwin.  Cost domination in graphs.  Ph.D. Thesis, Department of Mathematics, Western Michigan University, Kalamazoo, 2001.  https://scholarworks.wmich.edu/dissertations/1365/.
  * [8] D. J. Erwin.  Dominating broadcasts in graphs.  Bulletin of the ICA, 42:89–105, 2004.
  * [9] LLC Gurobi Optimization.  Gurobi optimizer reference manual, 2021.  http://www.gurobi.com.
  * [10] M. A. Henning, G. MacGillivray, and F. Yang.  Broadcast domination in graphs.  In T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, editors, Structures of Domination in Graphs, pages 15–46. Springer International Publishing, Cham, 2021.
  * [11] S. Herke.  Dominating broadcasts in graphs.  Master’s Thesis, University of Victoria, Victoria, 2007.  https://dspace.library.uvic.ca/handle/1828/1479.
  * [12] S. Herke and C. M. Mynhardt.  Radial trees.  Discrete Mathematics, 309(20):5950–5962, 2009.
  * [13] B. Park.  2-limited dominating broadcasts on cubic graphs without induced 4-cycles.  Discrete Applied Mathematics, 327:178–184, 2023.
  * [14] A. Slobodin.  $2$-limited broadcast domination on grid graphs.  Master’s Thesis, University of Victoria, Victoria, 2021.  http://hdl.handle.net/1828/13190.
  * [15] A. Slobodin.  C++ implementation of a method for proving lower bounds for the 2-limited broadcast domination number on grid graphs, 7 2022.  https://github.com/fastbodin/2-limited-broadcast-domination-grid-graph-prove-lower-bounds.
  * [16] A. Slobodin, G. MacGillivray, and W. Myrvold.  2-limited broadcast domination on grid graphs.  Discrete Applied Mathematics, 338:158–178, 2023.
  * [17] F. Yang.  New results on broadcast domination and multipacking.  Master’s Thesis, University of Victoria, Victoria, 2015.  https://dspace.library.uvic.ca/handle/1828/6627.
  * [18] F. Yang.  Limited broadcast domination.  Ph.D. Thesis, Department of Mathematics and Statistics, University of Victoria, Victoria, 2019.  https://dspace.library.uvic.ca/handle/1828/11444.
  * [19] F. Yang, G. MacGillivray, and R. C. Brewster.  Broadcast domination and multipacking in strongly chordal graphs.  Discrete Applied Mathematics, 261:108–118, 2019.