Leaky Zero Forcing on Subgraphs of $d$-dimensional Grid Graphs with an Application to Diamond Rectangles

Abstract

We study zero forcing and $\ell$-leaky zero forcing on Diamond rectangle graphs $DR(a,b)$, a family of induced subgraphs of 2-dimensional grid graphs. Motivated by this family, we develop more general results for subgraphs of $d$-dimensional grid graphs. Using $\ell$-leaky forts, we show that for $\ell \le 2d-1$, every nonempty $\ell$-leaky fort in a subgraph of $P_{n_1}\square \cdots \square P_{n_d}$ must contain a vertex of degree at most $2d-1$. This gives bounds and, in certain cases, exact values for the $\ell$-leaky forcing number of such subgraphs. We then apply these results to Diamond rectangle graphs, for which we show that the zero forcing number equals the maximum nullity and completely characterize the $\ell$-leaky forcing number for all $\ell \ge 1$.

arXiv commentMajor revision: added results on the structure of Diamond Rectangle Graphs, changed wording from "induced subgraphs" to only "subgraphs" and adjusted results accordingly