Track new results across pure and applied mathematics.
Search papers, labs, and topics across Lattice.
This paper establishes extremal theoretical bounds on the structural variation of zero forcing, an iterative vertex coloring process governing information diffusion and network controllability. The authors derive sharp upper bounds relative to graph order on both the cardinality discrepancy between minimal zero forcing sets and the variation in propagation times across minimum zero forcing sets. By constructing explicit infinite graph families that achieve these limits, the work settles the exact worst-case discrepancy achievable in discrete network propagation dynamics.
Zero forcing sets can exhibit maximal divergence in both size and propagation delay relative to graph order, establishing tight worst-case bounds on dynamic node infection processes.
Zero forcing is a process described by a color change rule on the vertices of a graph. In this paper, we maximize the discrepancy between various zero forcing parameters relative to graph order. First, we find an upper bound on the difference in cardinality between minimal zero forcing sets (sets containing no proper zero forcing subset) of maximum and minimum size, and we show that this bound is sharp for an infinite family of graphs. Furthermore, we derive an upper bound for the discrepancy between the maximum and minimum propagation times of the minimum zero forcing sets of any graph, showing this bound is sharp for an infinite family of graphs.