Pith. sign in

REVIEW 5 major objections 6 minor 3 references

On $(t,r)$ broadcast domination of certain grid graphs

T0 review · 5 major / 6 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper proves exact formulas for the (t,r) broadcast domination number of paths, finite grid graphs, and king's grid graphs via tilings by efficient two-tower starting blocks.

desk verdict The grid and king's-grid formulas are likely correct but the proofs don't establish minimality; this is a promising paper that needs a serious rewrite, not a desk reject. read the letter →

arxiv 1908.06189 v2 pith:CFXHUVEJ submitted 2019-08-16 math.CO

Natasha Crepeau , Pamela E. Harris , Sean Hays , Marissa Loving , Joseph Rennie , Gordon Rojas Kirby , Alexandro Vasquez This is my paper · ORCID
classification math.CO MSC 05C69
keywords (tr)broadcastdominationnumbergridgraphspathsking'sgraphslantstartingblockefficient
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Building on the (t,r) broadcast domination model, the paper asks how many strength-t towers are needed so that every vertex of a graph receives signal at least r. It proves exact answers for three families: paths, wide m×n grid graphs, and king's grid graphs with few rows. In each case the minimum is a ceiling of a linear ratio, with the ratio determined by the width of a two-tower block and the r−1 columns of overlap between consecutive blocks. These exact formulas reduce an optimization problem to arithmetic and extend earlier results that covered only small grids or gave upper bounds.

What carries the argument

The load-bearing object is the (t,r) starting block: a rectangular grid that two towers of strength t dominate with no wasted signal, so every vertex in the overlap receives exactly r. The arguments prove the dimensions of such a block in each family and then tile the graph with copies of it, inserting r−1 columns of overlap between consecutive blocks so no vertex falls below reception r. The overlap requirement comes from Lemma 2.1, which says any two consecutive towers must share at least r−1 vertices in their broadcast zones. The formulas are the arithmetic of this tiling: block width determines the denominator, starting towers determine the numerator offset, and the ceiling counts the last partial block.

What would settle it

Run an exhaustive search or integer program for a small case inside the theorem's range, for example G_{3,6} with (t,r)=(4,2), where the formula predicts 2+\lceil (6-5)/4 \rceil = 3 towers, and also G_{3,5}, where it predicts the base case of 2 towers. A minimum below the predicted value in either case would disprove the formula; equality in both is consistent with it.

Watch

Extended reading notes

Core claim

The central discovery is that optimal (t,r) broadcasts on these graphs are column-by-column tilings by an efficient two-tower block, and once the block's width is known the domination number follows by counting columns. For a path P_n the block has width 2t−r, giving γ_{t,r}(P_n) = \lceil (n+r-1)/(2t-r) \rceil. For an m×n grid with m≥2, 2t−r>m−1, and n≥2t−r−(m−2), the block width is 2t−r−(m−2), giving γ_{t,r}(G_{m,n}) = 2 + \lceil (n-(2t-r-(m-2)))/((2t-r-(m-2))-1) \rceil. For a king's grid with t>r and m≤2(t−r)+1, placing towers along the middle row makes the count match the path formula, γ_{t,r}(K_{m,n}) = \lceil (n+r-1)/(2t-r) \rceil. The same starting-block vocabulary produces upper bounds for 3D grids and for slant grids, and exact two-row slant counts.

Load-bearing premise

The grid and king's-grid formulas assume that an optimal dominating set can always be cut into identical two-tower starting blocks of the exact dimensions used in the constructions, with the proof of the grid block's base case left as an induction sketch that does not explicitly check reception at every vertex after the shift.

Editorial extensions

If this is right

  • For paths, the (t,r) broadcast domination number is now known for every t≥r≥1; the exact value is \lceil (n+r-1)/(2t-r) \rceil for all n≥1.
  • For m×n grids in the stated range, the number of towers grows linearly in the number of columns with slope 1/(2t−r−(m−1)), plus two towers for the starting block.
  • For king's grids with m≤2(t−r)+1, the diagonal edges do not lower the tower count below the path value; the middle row alone carries the domination.
  • For 3D grids, any rectangular box can be covered by copies of a two-tower starting block, giving the upper bound γ_{t,r}(G_{m,n,k})≤2B where B is the number of blocks needed.
  • For two-row slant grids, the exact count is \lceil 2(n+r-1)/(4t-2r-1) \rceil whenever t>r.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the starting-block tiling is optimal at every parameter value covered by the theorems, the same column-counting argument should yield exact formulas for wider king's-grid bands; the natural test is to increase m past 2(t−r)+1 and look for the threshold where diagonal edges begin to reduce the tower count.
  • The paper's path and king's-grid formulas both use the r−1 overlap rule, which suggests that cycles may often attain the upper bound given in Corollary 6.1; one could test whether γ_{t,r}(C_n) equals \lceil (n+r-1)/(2t-r) \rceil except when the closing of the cycle forces a larger last block.
  • The block widths in the grid theorem are all of the form 2t−r−(m−2), so the same machinery might give exact counts for other rectangular families with fixed row number m, replacing exhaustive search with a one-line formula once the correct starting block is identified.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 6 minor

Summary. The paper studies $(t,r)$ broadcast domination numbers for paths, rectangular grid graphs, 3D grid graphs, slant grids, and king's grids. It claims exact formulas for paths, grids, and king's grids, and upper bounds for 3D grids and slant grids. The constructions are based on 'starting blocks' efficiently dominated by two towers, which are then tiled across larger graphs. The paper also includes a SageMath algorithm for paths and several results on infinite king's lattices.

Significance. Explicit formulas for $(t,r)$ broadcast domination numbers would be a useful contribution to the literature, and the paper addresses natural families of graphs. However, the central exact-formula claims are not established: the proofs rely on unsupported tiling-optimality assumptions, and the grid formula is actually false. The 3D grid result is not a substantive quantitative bound because the quantity $B$ is never defined through a concrete covering algorithm. The paper does provide a constructive path algorithm, but the main theoretical results lack the necessary rigorous lower-bound arguments.

major comments (5)
  1. [§3, Theorem 1.2] Theorem 1.2 is false. For $t=2$, $r=1$, $m=3$, $n=5$, the formula claims $\gamma_{2,1}(G_{3,5}) = 2 + \lceil (5-2)/1 \rceil = 5$. But the set $D=\{(2,1),(1,3),(3,3),(2,5)\}$ of four towers is a $(2,1)$ broadcast dominating set of $G_{3,5}$: every vertex is at Manhattan distance at most 1 from one of these towers, hence receives signal at least 1. Thus $\gamma_{2,1}(G_{3,5}) \le 4 < 5$. The minimality proof in Section 3 only checks local efficiency of the constructed tiling and does not rule out alternative configurations with fewer towers.
  2. [§3, Lemma 3.2] Lemma 3.2 is not proven. The induction step from $G_{m,n}$ to $G_{m+1,n-1}$ asserts that shifting the second tower down one row and left one column preserves domination, but it does not provide tower coordinates or verify reception for every vertex. The claim that shifting the tower 'results in an efficiently dominated grid' is exactly what needs proof, and the lemma is load-bearing as the base of the tiling formula in Theorem 1.2.
  3. [§5.2, Lemma 5.4 and Theorem 1.4] The king's grid formula in Theorem 1.4 has the same two gaps. Lemma 5.4's induction on $t$ and $r$ is only sketched: it says to shift the first tower one column and the second tower four columns, but it never lists the resulting positions or checks all vertices. The lower-bound part of Theorem 1.4 argues that the first tower cannot move right and that starting blocks cannot be spread apart, which establishes only local optimality of the constructed configuration. It does not rule out a completely different dominating set with fewer towers, so no genuine lower bound is given.
  4. [§2, Theorem 1.1 and Lemma 2.1] The path formula is a main result, but its proof is informal. The lower-bound argument 'if we remove one tower, we lose one broadcast zone... shift the remaining towers... insufficient reception at the beginning or end' is not a rigorous counting argument. Lemma 2.1, which is used as the overlap estimate, also lacks a valid proof: the statement about $\gamma_{t,t-k}(P_n)$ does not establish a lower bound for an arbitrary dominating set. The formula may be true, but the manuscript does not provide a proof.
  5. [§4, Theorem 1.3 and Theorem 4.2] Theorem 1.3 is not a substantive upper bound because $B$ is never defined as a computable covering number, and no algorithm or existence argument for covering an arbitrary $G_{m,n,k}$ by starting blocks is given. Theorem 4.2's proof only checks vertices that lie inside the two broadcast zones and does not show that every vertex of the block lies in the union of those zones; moreover, the displayed equations assume both towers contribute to every vertex considered, which is not justified and is not true for vertices far from both towers.
minor comments (6)
  1. [§1, page 2] The definition of 'efficient broadcast' as 'minimizes wasted signal in the sense that every vertex in the overlap between multiple towers receives a signal of strength exactly r' is informal and not used as a formal definition in the proofs; please make it precise or remove it.
  2. [§3, Lemma 3.1] The induction in Lemma 3.1 is phrased confusingly: it simultaneously refers to induction on $t$ and on $r$ without a clear base case and induction step for each parameter. For example, 'Assume, by induction, that $\gamma_{t,1}(G_{2,(2t-1)})=2$' followed by 'we will show that $\gamma_{(t+1),1}$' mixes the two inductions.
  3. [§4, Theorem 4.2] There is a typo in the reception computation: the line for $r'(v')$ is missing a closing parenthesis and uses $t'$ where $t$ is intended. This makes the displayed formula hard to follow.
  4. [§5.2, Lemma 5.5] The explanation of the equal-diagonal case in the proof of Lemma 5.5 says 'you will have path length of $n + (n-1)$', but the shortest path length in the king's lattice when $|p-x|=|q-y|$ is $|p-x|$, not $n+(n-1)$. The lemma statement is correct, but the explanation is wrong.
  5. [§7, Appendix] The GitHub URL is not properly formatted: it contains a space ('t r path domination.git') and is not a clickable link.
  6. [§5.1, Theorem 5.4] The proof of the lower bound in Theorem 5.4 again asserts minimality from the local efficiency of the starting block ('if the towers were further apart, vertices... would have insufficient reception'), which does not rule out alternative configurations with fewer towers. Since this is an exact-formula claim, the same lower-bound concern applies as in Theorem 1.4.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the exact grid and king's-grid formulas are stated as theorems with constructive upper bounds and asserted (not derived) lower bounds; the lower-bound gaps are proof errors, not circular reductions.

full rationale

I find no load-bearing circular step that can be exhibited as an equation reducing to its own input. The path formula (Theorem 1.1) is a construction with a hand-wavy minimality argument; the grid formula (Theorem 1.2) and king's-grid formula (Theorem 1.4) similarly prove upper bounds by tiling starting blocks and then assert minimality because the blocks are 'efficient' (e.g., 'Therefore, if we made any of these blocks larger ... So, the dominating set we've constructed is minimal'). This is an unproved optimality claim comparing the construction only with its own perturbations, but it is not a case where the target formula is assumed in the construction or where a fitted parameter is renamed a prediction. The definition of 'efficient' as 'every vertex in the overlap ... receives a signal of strength exactly r' is not by definition 'minimum cardinality,' so the gap is a correctness/rigor problem, not self-definitional circularity. Lemma 3.2's induction is a sketched construction, not a circular use of Theorem 1.2. Theorem 1.3 is a trivial upper bound following from the definition of B and of a starting block; it is non-substantive but not a circular derivation of a predicted value. The only self-citation, [2] (Harris-Luque-Flores-Sepulveda), supplies an infinite triangular-lattice pattern used for slant-grid upper bounds (Theorem 5.2 and Table 1); the exact path, grid, and king's-grid theorems do not rely on it, and the cited pattern is a stated parameter-free construction from prior work. Thus no step meets the standard of 'Eq. X = Eq. Y by construction' or 'fitted input called prediction.' The paper's weaknesses are missing lower-bound proofs, which belong under correctness risk, not circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper introduces no fitted parameters. Its results rest on the inherited definition of (t,r) broadcasts, on the triangular lattice pattern from the self-cited [2], and on the unproven 'starting block' lemmas (3.2 and 5.4) that are load-bearing for the exact formulas. The king's lattice distance fact (Lemma 5.5) is true but its proof in the paper is incorrect.

assumptions (4)
  • domain assumption Definition of (t,r) broadcast domination and signal function f(v) = sum_{w in T} max(0, t - d(v,w)) from Blessing et al. [1].
    This is the object of study, inherited from the cited paper [1].
  • domain assumption Theorem 5.1 from Harris et al. [2]: the tower placement formula for the infinite triangular lattice is an efficient (t,r) broadcast domination pattern.
    Used as a black box to derive slant grid upper bounds. This is a self-citation (Pamela E. Harris is a co-author of both papers). It is not machine-checked and no proof is reproduced here.
  • ad hoc to paper Lemma 3.2 / Lemma 5.4: certain rectangular blocks are efficiently dominated by exactly two towers.
    These lemmas are proven by informal induction with no reception calculations for all vertices. They are load-bearing for Theorems 1.2 and 1.4.
  • domain assumption The distance in the king's lattice is max(|x-p|, |y-q|) (Lemma 5.5).
    This is true for the king's graph, but the proof provided in Lemma 5.5 is incorrect: it describes a path length of n+(n-1) for equal displacements, which is not how diagonal moves work.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On $(t,r)$ broadcast domination of certain grid graphs." pith.science (2026). https://pith.science/paper/CFXHUVEJ

@misc{pith2026190806189,
  author       = {Pith},
  title        = {Pith review of: On $(t,r)$ broadcast domination of certain grid graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CFXHUVEJ}},
  note         = {Machine review of arXiv:1908.06189}
}
abstract

Let $G=( V(G), E(G) )$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. We say a subset $D$ of $V(G)$ dominates $G$ if every vertex in $V \setminus D$ is adjacent to a vertex in $D$. A generalization of this concept is $(t,r)$ broadcast domination. We designate certain vertices to be towers of signal strength $t$, which send out signal to neighboring vertices with signal strength decaying linearly as the signal traverses the edges of the graph. We let $\mathbb{T}$ be the set of all towers, and we define the signal received by a vertex $v\in V(G)$ from a tower $w \in \mathbb T$ to be $f(v)=\sum_{w\in \mathbb{T}}max(0,t-d(v,w))$. Blessing, Insko, Johnson, Mauretour (2014) defined a $(t,r)$ broadcast dominating set, or a $(t,r) $ broadcast, on $G$ as a set $\mathbb{T} \subseteq V(G) $ such that $f(v)\geq r$ for all $v\in V(G)$. The minimal cardinality of a $(t, r)$ broadcast on $G$ is called the $(t, r)$ broadcast domination number of $G$. In this paper, we present our research on the $(t,r)$ broadcast domination number for certain graphs including paths, grid graphs, the slant lattice, and the king's lattice.

Figures

Figures reproduced from arXiv: 1908.06189 by the authors.

Figure 1
Figure 1. First Vertices of the Efficiently Dominated Path Proof. To construct an optimal dominating set by maximizing the size of a broadcast tower’s broadcast zone, we want the first vertex of the path to have reception r, as shown in [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. 2 2 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. A (2, 1) broadcast domination set for G2,2,5 with broadcast towers in red. Lemma 4.2. The (t, r) starting block for G2,2,k is a 2 × 2 × (2t − r − 1) grid when k ≥ 2t − r − 1. Proof. We will proceed by induction on r. Lemma 4.1 proves our base case of (t, r) = (t, 1). Assume γt,r(G2,2,(2t−r−1)) = 2. We will show γt,r(G2,2,(2t−r−2)) = 2. If we increase r to r + 1, then vertices that received a signal of r will no long… view at source ↗
Figures from the paper (14 more)
Figure 4
Figure 4. Figure 4: Shortest path between towers at positions (1, 1, k) and (m, n, 1). A pattern can be found between the sum of lengths of a 3D grid and its respective starting block. This relationship is made explicit in the following result. 6 [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Slant grid graph of S8,7. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png]
Figure 6
Figure 6. Figure 6: An efficient (2, 1) dominating pattern for the slant lattice. If we take a slice of the slant lattice with an efficient dominating pattern, as depicted in [PITH_FULL_IMAGE:figures/full_fig_p010_6.png]
Figure 7
Figure 7. Figure 7: A (2, 1) starting tile of the slant grid graph. Theorem 5.2. For Sm,n, if m = 2p and n = 8q, where p, q ∈ N, then γ2,1(Sm,n) ≤ (4q + 1)p. If m = 2p + ℓ for ℓ ∈ {0, 1} and n = 8q + k for k ∈ {0, 1, ..., 7}, then γ2,1(Sm,n) ≤ (4(q + 1) + 1)(p + 1) if both ℓ and k are non…
Figure 8
Figure 8. Figure 8: Slant grid graph dominated by 2 towers, for (2, 1). Proof. We construct the dominating set on S2,n as shown in the example in [PITH_FULL_IMAGE:figures/full_fig_p012_8.png]
Figure 9
Figure 9. Figure 9: Beginning of the constructed dominating set. We place our first tower on the top row and (t − r + 1)th column, as shown in [PITH_FULL_IMAGE:figures/full_fig_p013_9.png]
Figure 10
Figure 10. Figure 10: Dominating pattern for (2, 1) on K3,n. Using Lemma 5.4, we find an explicit formula for the domination number on the general finite king’s grid graph. Theorem 1.4. For t > r and m ≤ 2(t − r) + 1, then γt,r(Km,n) = l n+r−1 2t−r m . Proof. We first construct the dominat…
Figure 11
Figure 11. Figure 11: Spread of a tower in the king’s lattice. 1 1 1 [PITH_FULL_IMAGE:figures/full_fig_p016_11.png]
Figure 12
Figure 12. Figure 12: K1×1 constructed between two points by using as many diagonals as possible, which can be determined by min(|p − x|, |q − y|). This has 3 different cases, when |p − x| = |q − y|, |p − x| > |q − y|, and |p − x| < |q − y|. When |p − x| = |q − y|, we will have |p − x| dia…
Figure 13
Figure 13. Figure 13: Different cases for distance from two points. We now find an efficient dominating pattern on the king’s lattice for varying t and r = 1. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_13.png]
Figure 14
Figure 14. Figure 14: Plotting 6 towers in king’s lattice for (t, 1). Now, we consider the distance of any vertex in the infinite king’s lattice to a nearby tower. Given the symmetry of the tower placement and their broadcast zones it suffices to consider an arbitrary point (a, b) between …
Figure 15
Figure 15. Figure 15: Four towers in king’s lattice. ≤ max(|(t − 1) − 0|, |(t − 1) − 0|) ≤ max(|(t − 1)|, |(t − 1)|) ≤ t − 1. Thus, in both of the previous two cases (a, b) will receive signal at least 1 from v0. Suppose that t − 1 < a ≤ 3(t − 1) + 1 and −(t − 1) ≤ b ≤ (t − 1). When (a, b)…
Figure 16
Figure 16. Figure 16: Plotting 6 towers in K∞ for (t, 2). v3 v0 v1 v2 v4 [PITH_FULL_IMAGE:figures/full_fig_p020_16.png]
Figure 17
Figure 17. Figure 17: Five towers in king’s lattice. Consider [PITH_FULL_IMAGE:figures/full_fig_p020_17.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

3 extracted references · 3 canonical work pages

  1. [2]

    Broadcast Domination of Triangular Matchstick Graphs and the Triangular Lattice

    Pamela E. Harris, Dalia K. Luque, Claudia Reyes Flores, a nd Nohemi Sepulveda, Broadcast Domination of Tri- angular Matchstick Graphs and the Triangular Lattice , arXiv e-prints (2018Apr), arXiv:1804.07812, available a t 1804.07812. ↑2, 9, 10

    work page Pith review arXiv

  2. [1]

    On (t,r) Broadcast Domination Numbers of Grids

    David Blessing, Erik Insko, Katie Johnson, and Christie Mauretour, On (t,r) Broadcast Domination Numbers of Grids, arXiv e-prints (2014Jan), arXiv:1401.2499, available at 1401.2499. ↑1, 2, 3

    work page Pith review arXiv

  3. [3]

    Asymptotically Optimal Bounds for (t,2) Broadcast Domination on Finite Grids

    Timothy W. Randolph, Asymptotically Optimal Bounds for (t,2) Broadcast Dominat ion on Finite Grids , arXiv e-prints (2018May), arXiv:1805.06058, available at 1805.06058. ↑2 21 Department of Mathematics, Harvey Mudd College, United Sta tes E-mail address : ncrepeau@hmc.edu Department of Mathematics and Statistics, Williams Colleg e, United States E-mail ad...

    work page Pith review arXiv

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.