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

arXiv:2509.21529 · math.CO · Submitted 2025-09-25 · Read on arXiv

math.CO

Submitted: 2025-09-25

Updated: 2026-10-26

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

Code: https://github.com/rrmoruzzi/Leaky-Forcing-Algorithm

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study zero forcing and-leaky zero forcing on Diamond rectangle graphs DR(a,b), a family of induced subgraphs of 2-dimensional grid graphs.

Terminology

Abstract

We study zero forcing and-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-leaky forts, we show that for at most 2d-1, every nonempty-leaky fort in a subgraph of P n 1 P n d must contain a vertex of degree at most 2d-1. This gives bounds and, in certain cases, exact values for the-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-leaky forcing number for all at least 1.

Sources

Related papers