Minimal Zero Forcing Sets

Abstract

In this paper, we study minimal (with respect to inclusion) zero forcing sets. We first investigate when a graph can have polynomially or exponentially many distinct minimal zero forcing sets. We also study the maximum size of a minimal zero forcing set $\overline{Z}(G)$, and relate it to the zero forcing number $Z(G)$. Surprisingly, we show that the equality $\overline{Z}(G)=Z(G)$ is preserved by deleting a universal vertex, but not by adding a universal vertex. We also characterize graphs with extreme values of $\overline{Z}(G)$ and explore the gap between $\overline{Z}(G)$ and $Z(G)$.

13 pages, 3 figures