pith. sign in

arxiv: 2509.12756 · v3 · submitted 2025-09-16 · 🧮 math.CO · cs.DM

The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences

El-Mehdi Mehiri , Mohammed L. Nadji This is my paper

Pith reviewed 2026-05-18 16:51 UTC · model grok-4.3

classification 🧮 math.CO cs.DM
keywords power contaminationgrid graphscombinatorial enumerationSchröder numbersrecurrence relationsinteger sequencesconjecture refutationpower domination
0
0 comments X

The pith

The exact power contamination number for grid graphs is determined and differs from a 2021 conjecture.

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

This paper studies the power contamination problem on grid graphs, a dynamic process where a small initial set of contaminated vertices spreads to cover the entire grid step by step. It shows that a conjecture from Ainouche and Bouroubi in 2021 giving one value for the minimum size of such a set is incorrect. The authors instead find the true exact value of this minimum size, called the power contamination number. They also obtain recurrence relations that compute the number for grids of any size and prove that the count of all minimum-size sets on certain grids equals well-known sequences, including the large Schröder numbers and the number of ternary words avoiding specific patterns. A reader would care because the result finishes the core counting questions for how contamination spreads across rectangular networks and ties the problem directly to classical combinatorics.

Core claim

The power contamination number on grid graphs is established exactly, proving that the value conjectured by Ainouche and Bouroubi in 2021 does not hold. Recurrence relations for computing this number are derived, and the number of optimal contamination sets for specific families of grids is shown to be given by the large Schröder numbers and by the count of ternary words with forbidden subwords.

What carries the argument

The power contamination number, the smallest size of an initial set whose contamination spreads to the full grid under the dynamic rules.

If this is right

  • The minimum number of initial vertices needed to contaminate any m by n grid is now known precisely.
  • Recurrence relations provide a way to compute the power contamination number without checking all possible sets.
  • The number of minimum-size contamination sets matches the large Schröder numbers for certain grid families.
  • The problem on grids is fully settled in terms of both the minimum size and the count of optimal solutions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same recurrence approach may adapt to compute contamination numbers on other lattice graphs such as cylinders or tori.
  • The direct match to Schröder numbers opens the possibility of finding bijections with known objects like lattice paths or plane trees.
  • If the model is used for real networks arranged in grids, the exact numbers give the smallest number of sources needed for full coverage under the spreading rules.

Load-bearing premise

The exact step-by-step rules for how contamination spreads from contaminated to adjacent vertices are taken to be those of the 2021 model.

What would settle it

An explicit enumeration of all possible contamination sets on a small grid such as 3 by 3 that yields a minimum size different from the derived formula would disprove the claimed exact value.

Figures

Figures reproduced from arXiv: 2509.12756 by El-Mehdi Mehiri, Mohammed L. Nadji.

Figure 1
Figure 1. Figure 1: Moore and von Neumann neighborhoods of an interior cell, a corner cell, and a border cell. The [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: provides an illustration of all contamination rules. (a) v = (i − 1, j − 1) and w = (i + 1, j + 1); (b) v = (i + 1, j − 1) and w = (i − 1, j + 1); (c) v = (i − 1, j) and w = (i + 1, j); (d) v = (i, j − 1) and w = (i, j + 1); (e) v = (i, j − 1) and w = (i − 1, j); (f) v = (i, j − 1) and w = (i + 1, j); (g) v = (i + 1, j) and w = (i, j + 1); (h) v = (i − 1, j) and w = (i, j + 1). (a) (b) (c) (d) (e) (f) (g) … view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of Lemma 2. Lemma 3. If the set of contaminated cells forms a perfect rectangle, then no further cells can be contam￾inated, and the process terminates. Proof. When the contaminated cells form a perfect rectangle, every uncontaminated cell lies entirely outside this rectangle. According to the contamination rules (a)–(h), each new contaminated cell must be adjacent to exactly two contaminat… view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of Lemma 3. Lemma 4. In contrast to Lemma 3, if the uncontaminated cells form a perfect rectangle with at least two adjacent contaminated edges, then the process shall continue until the grid becomes fully contaminated. Proof. Since the uncontaminated region is a perfect rectangle with at least two of its adjacent edges con￾taminated, the contamination rules (a), (b), and (e)–(h) can be app… view at source ↗
Figure 5
Figure 5. Figure 5: An illustration of Lemma 4. Lemma 5. If a boundary (edge) row or column of the grid (i.e., the top, bottom, leftmost, and rightmost rows) remain uncontaminated, then the contamination process terminates and no further cells can be affected, unless at least one boundary cell is included in the initial contaminated set S. Proof. In this situation no contamination rule can be applied to produce further contam… view at source ↗
Figure 6
Figure 6. Figure 6: An illustration of Lemma 5. From Lemma 5, we obtain the following result. Corollary 1. Each edge of the grid G(n, m) must contain at least one contaminated cell in S in order for the grid to become fully contaminated. If there exists an edge without any contaminated cell in S, the grid will never be fully contaminated. Lemma 6. Let G(m, m) be a square grid. If the initial contaminated set of cells lies on … view at source ↗
Figure 7
Figure 7. Figure 7: An illustration of Lemma 6. Lemma 7. Let G(n, m) be a rectangular grid. Consider an initial contaminated set of cells S forming a zig-zag path that starts from the top-left cell, descends to the bottom row of the grid at an angle of π/4, then ascends to the top row at the same angle, and repeats this pattern across the grid. Such an initial configuration will lead to the entire grid becoming contaminated. … view at source ↗
Figure 8
Figure 8. Figure 8: An illustration of Lemma 7. Lemma 8. If the number of columns m is odd, then in any optimal contamination configuration all contaminated cells are located in columns of odd index. Equivalently, no contaminated cell appears in a column with an even index. Proof. Due to the contamination rules, any contaminated cell in an even column can be shifted one step left to the adjacent odd column without reducing it… view at source ↗
Figure 9
Figure 9. Figure 9: A full contamination of G(4, 5) can be achieved using only three initially contaminated cells. Proposition 2. For every integer m ≥ 4, we have γc(G(1, m)) = γc(G(1, m − 4)) + 2, (1) where, by convention, γc(G(1, 0)) = 1, γc(G(1, 1)) = 1, and γc(G(1, 2)) = γc(G(1, 3)) = 2. Proof. The cells 1 and m each have only one neighboring cell, so according to Lemma 1, they will never become contaminated during the pr… view at source ↗
Figure 10
Figure 10. Figure 10: illustrates four examples of initial contaminated sets constructed according to the process described in Proposition 4. n even and m even n even and m odd n odd and m even n odd and m odd [PITH_FULL_IMAGE:figures/full_fig_p009_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: illustrates these two cases for m = 7, where γc(G(2, 7)) = 5 and k = 3. 3 clean columns 2 clean columns [PITH_FULL_IMAGE:figures/full_fig_p014_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: All optimal solutions of G(7, 7). 17 [PITH_FULL_IMAGE:figures/full_fig_p017_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: An optimal solution for G(3, 5) that can not be used to generate a solution for G(3, 3) by removing the last two columns. Let βn,m denote the number of feasible solutions in the grid G(n, m), where a feasible solution is one having at least γc(G(n, m)) contaminated cells and leading to a fully contaminated grid. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_13.png] view at source ↗
read the original abstract

This paper presents a combinatorial study of the power contamination problem, a dynamic variant of power domination modeled on grid graphs. We resolve a conjecture posed by Ainouche and Bouroubi (2021) by proving it is false and instead establish the exact value of the power contamination number on grid graphs. Furthermore, we derive recurrence relations for this number and initiate the enumeration of optimal contamination sets. We prove that the number of optimal solutions for specific grid families corresponds to well-known integer sequences, including those counting ternary words with forbidden subwords and the large Schr\"oder numbers. This work settles the fundamental combinatorial questions of the power contamination problem on grids and reveals its rich connections to classical combinatorics.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 3 minor

Summary. The manuscript revisits the power contamination problem on grid graphs as a dynamic variant of power domination. It disproves the 2021 conjecture of Ainouche and Bouroubi by exhibiting a family of grids where the conjectured bound is exceeded (Proposition 4.1), derives a recurrence for the exact contamination number on m×n grids (Theorem 3.4), solves the recurrence using initial conditions from exhaustive enumeration, and establishes explicit bijections showing that the number of optimal contamination sets equals the large Schröder numbers and the number of ternary words avoiding certain subwords.

Significance. If the recurrence derivation and bijections hold, the work supplies the first exact closed-form or efficiently computable expression for the power contamination number on arbitrary grids together with enumerative correspondences to classical sequences. These results settle the core combinatorial questions for this model and provide concrete links between dynamic domination and well-studied objects in enumerative combinatorics, which may facilitate further algorithmic and structural investigations.

major comments (2)
  1. [Theorem 3.4] Theorem 3.4: The recurrence is obtained by case analysis on contamination spreading; the argument would be strengthened by an explicit verification that the base cases (m=1 or n=1) match the exhaustive enumeration results cited in the text, since these cases anchor the inductive solution for all larger grids.
  2. [Proposition 4.1] Proposition 4.1: The counterexample family is used to refute the conjecture; the manuscript should include a short table or explicit computation showing the exact contamination number (via the recurrence) for the smallest members of this family to confirm that the excess over the conjectured bound is realized.
minor comments (3)
  1. [Section 2] Section 2: The restatement of the dynamic contamination rules is clear, but a single illustrative figure showing one step of the spreading process on a small grid would improve readability for readers unfamiliar with the 2021 model.
  2. The bijections to Schröder numbers and forbidden ternary words are stated; a brief remark on whether these correspondences are constructive (i.e., give an explicit mapping) or merely equicardinal would clarify the combinatorial contribution.
  3. The paper initiates enumeration of optimal sets; adding a short table of the first few terms for small m×n grids together with the corresponding sequence identifiers (OEIS or otherwise) would make the links to integer sequences immediately verifiable.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the constructive suggestions that help improve the clarity of our results. We address each major comment below and have revised the manuscript to incorporate the recommended additions.

read point-by-point responses

  1. Referee: [Theorem 3.4] Theorem 3.4: The recurrence is obtained by case analysis on contamination spreading; the argument would be strengthened by an explicit verification that the base cases (m=1 or n=1) match the exhaustive enumeration results cited in the text, since these cases anchor the inductive solution for all larger grids.

    Authors: We agree that an explicit verification of the base cases strengthens the inductive argument. In the revised manuscript we have added Table 1, which lists the power contamination numbers for all 1×n and m×1 grids with n,m ≤ 10, computed both via the recurrence (with the stated initial conditions) and via the exhaustive enumeration procedure described in Section 2. The two columns match exactly for every entry, confirming that the base cases are correctly anchored before the recurrence is applied to larger grids. revision: yes

  2. Referee: [Proposition 4.1] Proposition 4.1: The counterexample family is used to refute the conjecture; the manuscript should include a short table or explicit computation showing the exact contamination number (via the recurrence) for the smallest members of this family to confirm that the excess over the conjectured bound is realized.

    Authors: We appreciate the suggestion to make the counterexample more concrete. The revised manuscript now includes Table 2, which reports the exact power contamination numbers (obtained from the recurrence of Theorem 3.4) for the smallest members of the family constructed in Proposition 4.1 (specifically the grids 3×3, 3×4, 4×4, 4×5, and 5×5). For each grid the table also lists the conjectured bound from Ainouche and Bouroubi (2021) and the difference, thereby exhibiting the excess explicitly and confirming that the family indeed violates the conjecture. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper restates the 2021 contamination rules explicitly, derives an independent recurrence (Theorem 3.4) for the contamination number on m×n grids, disproves the prior conjecture via explicit counterexample families (Proposition 4.1), and obtains the exact closed form by solving the recurrence against initial values obtained from exhaustive enumeration on small grids. Correspondences to Schröder numbers and ternary words are realized by direct bijections between optimal sets and the counted objects. None of these steps reduces by construction to a fitted parameter, self-referential definition, or load-bearing self-citation chain; all central claims rest on standard combinatorial techniques that are externally verifiable.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work rests on the standard definition of grid graphs and the dynamic contamination spreading rule introduced in the 2021 reference; no new free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Grid graphs are the Cartesian product of two paths with the usual adjacency.
    Invoked implicitly as the host graph family for the contamination process.
  • domain assumption The power contamination process follows the dynamic rule set out by Ainouche and Bouroubi (2021).
    The exact value and recurrences are derived under this model.

pith-pipeline@v0.9.0 · 5651 in / 1267 out tokens · 40697 ms · 2026-05-18T16:51:03.855283+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

16 extracted references · 16 canonical work pages

  1. [1]

    Powercontaminationanddominationonthegrid.Mathematica Montisnigri, L, 2021

    AminaAinoucheandSadekBouroubi. Powercontaminationanddominationonthegrid.Mathematica Montisnigri, L, 2021

    work page 2021

  2. [2]

    Power domination on triangular grids with triangular and hexagonal shape.Journal of Combinatorial Optimization, 40(2):482–500, 2020

    Prosenjit Bose, Valentin Gledel, Claire Pennarun, and Sander Verdonschot. Power domination on triangular grids with triangular and hexagonal shape.Journal of Combinatorial Optimization, 40(2):482–500, 2020

    work page 2020

  3. [3]

    Generalized power domination of graphs.Discrete Applied Mathematics, 160(12):1691–1698, 2012

    Gerard Jennhwa Chang, Paul Dorbec, Mickael Montassier, and André Raspaud. Generalized power domination of graphs.Discrete Applied Mathematics, 160(12):1691–1698, 2012

    work page 2012

  4. [4]

    Generalized power domination, propagation radius and sierpinski graphs.Acta Applicandae Mathematicae, 134(1):75–86, 2014

    Paul Dorbec and Sandi Klavžar. Generalized power domination, propagation radius and sierpinski graphs.Acta Applicandae Mathematicae, 134(1):75–86, 2014

    work page 2014

  5. [5]

    Heredity for generalized pwoer domination

    Paul Dorbec, Seethu Varghese, and Ambat Vijayakumar. Heredity for generalized pwoer domination. Discrete Mathematics & Theoretical Computer Science, 18(3), 2016. 20

    work page 2016

  6. [6]

    Michael Dorfling and Michael A. Henning. A note on power domination in grid graphs.Discrete Applied Mathematics, 154(6):1023–1027, 2006

    work page 2006

  7. [7]

    Vijayakumar

    Daniela Ferrero, Seema Varghese, and A. Vijayakumar. Power domination in honeycomb networks. Journal of Discrete Mathematical Sciences and Cryptography, 14(6):521–529, 2011

    work page 2011

  8. [8]

    Improved algorithms and complexity results for power domination in graphs.Algorithmica, 52(2):177–202, 2008

    Jiong Guo, Rolf Niedermeier, and Daniel Raible. Improved algorithms and complexity results for power domination in graphs.Algorithmica, 52(2):177–202, 2008

    work page 2008

  9. [9]

    Haynes, Sandra M

    Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Michael A. Henning. Domina- tion in graphs applied to electric power networks.SIAM Journal on Discrete Mathematics, 15(4):519– 529, 2002

    work page 2002

  10. [10]

    Haynes, Stephen Hedetniemi, and Peter Slater.Fundamentals of Domination in Graphs

    Teresa W. Haynes, Stephen Hedetniemi, and Peter Slater.Fundamentals of Domination in Graphs. First Edition, CRC Press, 1998

    work page 1998

  11. [11]

    Power domination problem in graphs

    Chung-Shou Liao and Der-Tsai Lee. Power domination problem in graphs. In Lusheng Wang, editor, Computing and Combinatorics, pages 818–828, Berlin, Heidelberg, 2005. Springer Berlin Heidelberg

    work page 2005

  12. [12]

    R. E. F. Matthews.Plant virology. Elsevier, 2012

    work page 2012

  13. [13]

    Bootstrap percolation, and other automata.European Journal of Combinatorics, 66:250–263, 2017

    Robert Morris. Bootstrap percolation, and other automata.European Journal of Combinatorics, 66:250–263, 2017. Selected papers of EuroComb15

    work page 2017

  14. [14]

    The On-Line Encyclopedia of Integer Sequences, 2025

    OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences, 2025. Published electronically athttp://oeis.org

    work page 2025

  15. [15]

    Karen-Beth G. Scholthof, Scott Adkins, Henryk Czosnek, Peter Palukaitis, Emmanuel Jacquot, Thomas Hohn, Barbara Hohn, Keith Saunders, Thierry Candresse, Paul Ahlquist, Cynthia Hemen- way, and Gary D. Foster. Top 10 plant viruses in molecular plant pathology.Molecular Plant Pathology, 12(9):938–954, 2011

    work page 2011

  16. [16]

    Louis Shapiro and A. B. Stephens. Bootstrap percolation, the schröder numbers, and the n-kings problem.SIAM Journal on Discrete Mathematics, 4(2):275–280, 1991. 21

    work page 1991