Failed Zero Forcing Numbers of Trees and Circulant Graphs - Luis Gomez; Karla Rubi; Jorden Terrazas; Rigoberto Florez; Darren A. Narayan (Theory and Applications of Graphs)
Given a graph $G$, the zero forcing number of $G$, $Z(G)$, is the smallest cardinality of any set $S$ of vertices on which repeated applications of the forcing rule (described below) results in all vertices being in $S$. The forcing rule is as follows: if a vertex $v$ is in $S$, and exactly one neighbor $u$ of $v$ is not in $S$, then $u$ is added to $S$ in the next iteration. Zero forcing numbers have attracted great interest over the past 15 years and have been well studied. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by $G$. In this paper we investigate the largest size of a set $S$ that does not force all of the vertices in a graph to be in $S$. This property is known as the failed zero forcing number of a graph and will be denoted by $F(G)$. This property has been investigated in recent years, including a proof by Shitov that the determination of $F(G)$ is NP-complete. In this paper we present new results involving $F(G)$ for trees including a lower bound based on the independence number. In addition we develop new extremal methods and use them determine $F(G)$ for families of circulant graphs.