A Lower Bound on the Failed Zero Forcing Number of a Graph

Abstract

Given a graph $G=(V,E)$ and a set of vertices marked as filled, we consider a color-change rule known as zero forcing. A set $S$ is a zero forcing set if filling $S$ and applying all possible instances of the color change rule causes all vertices in $V$ to be filled. A failed zero forcing set is a set of vertices that is not a zero forcing set. Given a graph $G$, the failed zero forcing number $F(G)$ is the maximum size of a failed zero forcing set. An open question was whether given any $k$ there is a an $\ell$ such that all graphs with at least $\ell$ vertices must satisfy $F(G)\ge k$. We answer this question affirmatively by proving that for a graph $G$ with $n$ vertices, $F(G)\ge \lfloor \frac{n-1}{2}\rfloor$.

11 pages, 13 figures. Comments welcome