Leaky Zero Forcing on Subgraphs of d-dimensional Grid Graphs with an Application to Diamond Rectangles
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality