REVIEW 3 major objections 4 minor 7 references
Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids
T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The (t,r) broadcast domination analogue of Vizing's conjecture fails for reception threshold at least 2, with explicit cycle-square counterexamples.
desk verdict The (t,r) Vizing counterexample is real and the main math holds, but the bijection proof and the algorithm's correctness argument both contain fixable errors. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
Two mechanisms carry the argument. For the counterexample, the load-bearing identity is the antipodal-pair reception on $C_n \Box C_n$: with $n = 2(t-r+1)$, the distances from any vertex to the two broadcasts at $(0,0)$ and $(n/2,n/2)$ sum to $n$, giving reception $2t-n = 2r-2$, which clears the threshold $r$ precisely when $r \ge 2$. For the density results, the machinery is the tower set $T(d,e) = \{(md+ne, n) : m,n \in \mathbb{Z}\}$, a periodic lattice of broadcasts of density $1/d$, together with the unwasted-coverage function $C_{t,r}(\mathbb{Z}^n)$ that caps how much reception one broadcast can contribute and yields the lower bound $\gamma_{t,r}(G) \ge r|V|/C_{t,r}(\mathbb{Z}^n)$.
What would settle it
Take $(t,r)=(4,2)$, so $n=6$: a single broadcast at $(0,0)$ leaves $(3,0)$ with reception $1<2$, while broadcasts at $(0,0)$ and $(3,3)$ give every vertex of $C_6 \Box C_6$ reception exactly $2$. If either part fails, Theorem 4's counterexample collapses; for the density tables, a non-tower periodic pattern that dominates with density below the table's value would show those numbers are only tower-set minima.
Extended reading notes
Core claim
On the paper's own terms, the discovery is a negative answer to the natural broadcast version of Vizing's conjecture. Fix $t \ge r \ge 2$ and let $n = 2(t-r+1)$. In the cycle $C_n$, one broadcast leaves the antipodal vertex with reception $r-1$, so $\gamma_{t,r}(C_n)=2$. In the Cartesian square $C_n \Box C_n$, two broadcasts placed at $(0,0)$ and $(n/2,n/2)$ dominate: for every vertex, the two distances to those broadcasts sum to $n$, so the total reception is $t-d_1 + t-d_2 = 2t-n = 2r-2 \ge r$, while a single broadcast still leaves $(n/2,0)$ undominated. Hence $\gamma_{t,r}(C_n \Box C_n)=2 < \gamma_{t,r}(C_n)\gamma_{t,r}(C_n)=4$. The paper supports this with the conjecture that a factor $1/2$ lower bound holds for all $t,r$, and that the $r=1$ (distance-domination) case satisfies the original Vizing inequality. Alongside this, it proves formulas for $|S_n(d)|$ and generating functions, the bijection between $B_n(d)$ and $B_d(n)$, a coverage lower bound $\gamma_{t,r}(G) \ge r|V|/C_{t,r}(\mathbb{Z}^n)$, and an algorithm over tower sets $T(d,e)$.
Load-bearing premise
The density tables rest on the search's assumption that checking only vertices $(i,0)$ for $t-r+1 \le i \le d/2$ catches every undominated vertex because the periodic broadcast pattern is symmetric under $(x,y) \mapsto (-x,y)$; if that symmetry fails, the search can certify a non-dominating pattern as dominating.
Editorial extensions
If this is right
- For every $t \ge r \ge 2$, the graph $C_n \Box C_n$ with $n = 2(t-r+1)$ has $\gamma_{t,r}(C_n \Box C_n)=2 < 4 = \gamma_{t,r}(C_n)\gamma_{t,r}(C_n)$, so the product lower bound proposed in Question 2 is false.
- The counterexample family has product ratio 2, so if Conjecture 5 is true its factor $1/2$ is tight for this family; no stronger constant of Vizing type can hold for all $(t,r)$ broadcasts with $r \ge 2$.
- The coverage bound $\gamma_{t,r}(G) \ge r|V|/C_{t,r}(\mathbb{Z}^n)$ applies to every finite $n$-dimensional grid subgraph and gives a universal lower bound on the number of broadcasts needed.
- The tower-set algorithm returns explicit periodic dominating patterns; for $r=1$ the returned density matches the lower bound, so these are optimal among tower sets, and the table values agree with previously known results.
- The bijection between $B_n(d)$ and $B_d(n)$ means any conclusion that depends only on ball sizes is symmetric in dimension and radius.
Reading between the lines
- Editorial extension: if the bijection between $B_n(d)$ and $B_d(n)$ is combined with the coverage bound, domination densities for parameters $(n; t,r)$ may be compared with those for $(t; n,r)$; a concrete test is to compute $C_{n,r}(\mathbb{Z}^t)$ and compare it with $C_{t,r}(\mathbb{Z}^n)$.
- Editorial extension: Conjecture 6 with $t=2$ is the original Vizing conjecture, since ordinary domination is $(2,1)$ broadcast domination, so a proof for all $t$ would settle the classical conjecture as a special case.
- Editorial extension: the paper's density tables are restricted to periodic tower patterns, so a natural test is whether a non-tower periodic pattern can achieve lower density than the table values; if one does, the tables are upper bounds rather than global minima.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies (t,r) broadcast domination on graphs, with emphasis on grid graphs. It proves that the natural analog of Vizing's conjecture fails for r≥2 by exhibiting cycles C_n with n=2(t−r+1) for which γ_{t,r}(C_n□C_n)=2<γ_{t,r}(C_n)^2=4 (Section 2). It then derives formulas and generating functions for the sizes of distance balls in Z^n, including a claimed bijection between B_n(d) and B_d(n) (Section 3), proves a double-counting lower bound on the domination density of grids (Section 4), and gives an algorithm that searches over periodic 'tower' broadcast patterns to compute densities, with a table of reciprocal densities for t,r≤9 (Section 5, Table 3).
Significance. The main conceptual contribution is the counterexample family to the (t,r)-broadcast generalization of Vizing's conjecture: it is correct, simple, and explicitly disproves a natural conjecture for all r≥2. The ball-counting identities, generating functions, and Delannoy-number connection are useful additions to the broadcast-domination toolkit, and the coverage double-counting lower bound (Theorem 17) is a clean argument. The paper also extends the computational method of Drews–Harris–Randolph to more dimensions and reports a speedup. However, the computational section is not yet in final form: the stated symmetry justification for Algorithm 1 is false, and the pseudocode contains internal inconsistencies. These issues are repairable, but the current manuscript does not provide a correct published certificate for Table 3.
major comments (3)
- [Section 5, paragraph after Algorithm 1] The justification for checking only vertices (i,0) with i≤d/2 is incorrect. The broadcast set T(d,e) is not invariant under (x,y)→(−x,y): for T(18,5), the point (5,1) belongs to the tower set, but (−5,1) does not. The reduction can instead be proved from central inversion (x,y)→(−x,−y), which does preserve T(d,e), together with the translation equivalence (x,y)→(x−ye,0); these imply that reception at (−i,0) equals reception at (i,0) and that every vertex is domination-equivalent to an x-axis representative. Please replace the stated reflection argument with this correct version, since the correctness proof of the algorithm is otherwise invalid as written.
- [Section 5, Algorithm 1 and preceding text] The pseudocode is not internally consistent. MaxPotentialD is written as floor(1/γ_{t,r}(G)) ≤ C_{t,r}(Z^n)/(r|V|), but Example 18 uses d starting at floor(C_{t,r}/r)=19 for (t,r)=(4,2), which is the quantity that makes sense. In addition, procedure MinDensity calls Rebroadcast, which is never defined, while the defined procedure is IsBroadcast. These discrepancies mean the published text is not a faithful certificate for Table 3; they should be corrected, and the authors should supply the actual code or machine-checkable output to support the tabulated values.
- [Section 3, Theorem 15 proof] The proof says that ψ is defined by reversing the order of the signed tuples, but reversing order does not map T_{n,d} to T_{d,n}, since it leaves both the dimension sum and the distance sum unchanged. Example 14 shows that the intended map swaps the two entries in each tuple, which is what interchanges the two sums. Please correct the proof of Theorem 15 to match the map used in the example.
minor comments (4)
- [Section 3, Theorem 12] The displayed formula for S_d(x) has (1+x)^{d+1} as the denominator; the first displayed expression in the proof and the analogous formula for S_n(y) show that the denominator should be (1−x)^{d+1}. The condition 'for x>0' should also be removed.
- [Section 5, pseudocode for IsBroadcast] The initialization a[i]=a[−i]=t−i relies on an implicit wrap-around convention for negative indices; the pseudocode should state explicitly that a[−i] means a[d−i] for 1≤i<t.
- [Section 4, Lemma 16 proof] The sentence 'where the second equality comes from plugging in the cardinality |S_n(d)| from Theorem 7' refers to a second equality that is not present in the displayed formula; the sentence should be reworded or removed.
- [Section 5, data availability] The phrases 'found here' for the code and more complete data should be replaced by permanent references, an appendix, or a stable repository link, so the computational results can be independently checked.
Circularity Check
No circularity: the Vizing counterexample is a direct construction, the lower bound is a coverage double-count, and the Section 5 search is an exhaustive algorithm rather than a fitted prediction.
full rationale
The paper's derivation chain is self-contained and contains no step in which a claimed prediction reduces, by definition or by fitted parameter, to its own inputs. Section 2 proves the (t,r) analog of Vizing's conjecture is false for r>=2 by explicitly placing two broadcasts at opposite corners of C_n square C_n, computing the reception 2t-n = 2r-2 for every vertex, and separately showing one broadcast cannot dominate because (n/2,0) receives only r-1. This is a direct construction, not an assumption of the target inequality. Section 3 derives the lattice-ball counting formulas with proofs included; the connection to Delannoy numbers is acknowledged as previously found by Zaitsev and is not load-bearing for the paper's domination results. Section 4 proves a lower bound by double-counting: the total required reception is r|V|, each broadcast supplies at most C_{t,r}(Z^n) unwasted reception, so gamma >= r|V|/C. This bound does not assume the density it is used to bound. Section 5's algorithm is an exhaustive search over the tower-set ansatz explicitly adopted from Drews-Harris-Randolph; it finds the largest d for which T(d,e) dominates by simulating receptions, and reports 'reciprocal of minimum density' only among tower sets, not as a universally optimal density obtained from fitted data. There are no fitted parameters, and the citations to prior work are external, with the present author not a coauthor, so no self-citation chain is load-bearing. One non-circular correctness caveat exists: the stated invariance under (x,y)->(-x,y) for T(d,e) is false in general, as T(18,5) contains (5,1) but not (-5,1); however, the algorithm's pruning can be justified by the lattice-translation quotient and central inversion, and this is a proof-repair issue, not circular reasoning. The printed MaxPotentialD formula also contains a typo, but Example 18 shows the implemented bound is C/r, derived from Lemma 16. These defects affect certification of Table 3, not the circularity of the derivation.
Assumptions & free parameters
assumptions (4)
- standard math The graph distance in the Cartesian product of paths (grid Z^n) is the L1 (Manhattan) distance, and the reception from a broadcast decays linearly as t - dist.
- domain assumption Capping per-vertex reception at r does not change whether a vertex is dominated, so total unwasted reception in a dominated graph is at least r|V|.
- domain assumption The algorithm restricts to periodic tower sets T(d,e) of density 1/d; it does not assume these contain the globally optimal pattern for r>1, only that they produce valid upper bounds.
- domain assumption The reception function on the quotient of Z^2 by the tower lattice is symmetric under x -> -x, so checking vertices (i,0) for i in [0, floor(d/2)] suffices.
Cite this review
Pith. "Pith review of Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids." pith.science (2026). https://pith.science/paper/4DDZUOCG
@misc{pith2026190807586,
author = {Pith},
title = {Pith review of: Bounds On $(t,r)$ Broadcast Domination of $n$-Dimensional Grids},
year = {2026},
howpublished = {\url{https://pith.science/paper/4DDZUOCG}},
note = {Machine review of arXiv:1908.07586}
}
abstract
In this paper, we study a variant of graph domination known as $(t, r)$ broadcast domination, first defined in Blessing, Insko, Johnson, and Mauretour in 2015. In this variant, each broadcast provides $t-d$ reception to each vertex a distance $d < t$ from the broadcast. If $d \ge t$ then no reception is provided. A vertex is considered dominated if it receives $r$ total reception from all broadcasts. Our main results provide some upper and lower bounds on the density of a $(t, r)$ dominating pattern of an infinite grid, as well as methods of computing them. Also, when $r \ge 2$ we describe a family of counterexamples to a generalization of Vizing's Conjecture to $(t,r)$ broadcast domination.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
On ( t, r) broadcast domination numbers of grids
David Blessing, Erik Insko, Katie Johnson, and Christie Mauretou r. On ( t, r) broadcast domination numbers of grids. Discrete Appl. Math. , 187:19–40, 2015
work page 2015
-
[2]
Boˇ stjan Breˇ sar, Paul Dorbec, Wayne Goddard, Bert L. Har tnell, Michael A. Henning, Sandi Klavˇ zar, and Douglas F. Rall. Vizing’s conjecture: a survey and rec ent results. J. Graph The- ory, 69(1):46–76, 2012
work page 2012
-
[3]
Benjamin F. Drews, Pamela E. Harris, and Timothy W. Randolph. Op timal ( t, r) broadcasts on the infinite grid. Discrete Appl. Math. , 255:183–197, 2019
work page 2019
-
[4]
New upper bounds on the dista nce domination numbers of grids
Michael Farina and Armando Grez. New upper bounds on the dista nce domination numbers of grids. Rose-Hulman Undergrad. Math. J. , 17(2):Art. 7, 133–145, 2016
work page 2016
-
[5]
Teresa W. Haynes, Stephen T. Hedetniemi, and Peter J. Slater. Fundamentals of domination in graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics . Marcel Dekker, Inc., New York, 1998
work page 1998
-
[6]
V. G. Vizing. Some unsolved problems in graph theory. Uspehi Mat. Nauk , 23(6 (144)):117–134, 1968
work page 1968
-
[7]
Dmitry A. Zaitsev. A generalized neighborhood for cellular automa ta. Theoret. Comput. Sci. , 666:21–35, 2017. Florida Gulf Coast University E-mail address : tshlomi1836@eagle.fgcu.edu
work page 2017
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.