The zero forcing polynomial of a graph (Q1732095)

Let $G$ be a graph. If $S \subseteq V(G)$ is a set of initially colored vertices, then the zero forcing color change rule demands that at each timestep, a colored vertex $u$ with a single uncolored neighbor $v$ forces that neighbor to become colored. The closure of $S$ is the set of colored vertices obtained after the color change rule is applied in timesteps until no new vertex can be forced in a timestep. A zero forcing set is a set whose closure is all $V$. In the present paper, the authors introduce the zero forcing polynomial of a graph. \par Definition. Let $G$ be a graph on $n$ vertices and $z(G;i)$ be the number of zero forcing sets of $G$ with cardinality $i$. The zero forcing polynomial of $G$ is defined as \[ \mathcal{Z}(G;x) = \sum_{i=1}^n z(G;i)x^i. \] Obviously, the defined polynomial is related to the zero forcing number of $G$, denoted by $Z(G)$, which is defined as the minimum cardinality of a zero forcing set. \par In the paper, the extremal coefficients of the zero forcing polynomial are firstly studied in Section 3. In the following section, the polynomial is investigated for some specific families of graphs, for example complete graphs, paths, cycles, wheels, and threshold graphs. Finally, in Section 5, various structural properties of the zero forcing polynomial are examined (such as multiplicativity, unimodality, uniqueness). In addition, several families of graphs which can be recognized by their zero forcing polynomials are identified. However, it does not hold in general that if $\mathcal{Z}(G;x) = \mathcal{Z}(H;x)$, then $G \backsimeq H$. In the conclusion, some interesting open problems are also presented. Among them, the following question is included: for any graph $G$ on $n$ vertices, is it true that $z(G;i) \leq z(P_n;i)$, for $1 \leq i \leq n$?