The zero forcing number of graphs with a given

Randy Davila, Thomas Malinowski, Sudeep Stephen

Published 2016-11-20Version 1

In this note, we study a dynamic coloring of vertices in a simple graph $G$. In particular, one may color an initial set of vertices, with all other vertices being non-colored. Then, at each discrete time step, a colored vertex with exactly one non-colored neighbor will force its non-colored neighbor to become colored. The initial set of colored vertices is called a \emph{forcing set} (\emph{zero forcing set}) if be iterating this aforementioned process, all of the vertices in $G$ become colored. The \emph{forcing number} (\emph{zero forcing number}) of $G$ is the cardinality of a minimum forcing set in $G$, and is denoted by $F(G)$. The main contribution of this note is to prove the following conjecture originally posed by Davila and Kenter in \cite{Davila Kenter}, and partially resolved in \cite{Davila Henning, Davila Kenter, Genter1, Genter2}; namely, if $G$ is a graph with minimum degree $\delta \ge 2$ and girth $g \ge 3$, then $F(G) \ge \delta + (\delta - 2)(g - 3)$.