The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914459996389376 |
|---|---|
| author | Mehiri, El-Mehdi Nadji, Mohammed L. |
| author_facet | Mehiri, El-Mehdi Nadji, Mohammed L. |
| contents | 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öder numbers. This work settles the fundamental combinatorial questions of the power contamination problem on grids and reveals its rich connections to classical combinatorics. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_12756 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences Mehiri, El-Mehdi Nadji, Mohammed L. Combinatorics Discrete Mathematics 05C69, 05C57, 05A15, 05C30, 92D30, 05A05 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öder numbers. This work settles the fundamental combinatorial questions of the power contamination problem on grids and reveals its rich connections to classical combinatorics. |
| title | The Power Contamination Problem on Grids Revisited: Optimality, Combinatorics, and Links to Integer Sequences |
| topic | Combinatorics Discrete Mathematics 05C69, 05C57, 05A15, 05C30, 92D30, 05A05 |
| url | https://arxiv.org/abs/2509.12756 |