Grundy domination and zero forcing in regular graphs

Abstract

Given a finite graph $G$, the maximum length of a sequence $(v_1,\dots ,v_k)$ of vertices in $G$ such that each $v_i$ dominates a vertex that is not dominated by any vertex in $\{v_1,\dots ,v_{i-1}\}$ is called the Grundy domination number, ${\gamma }_{\mathrm{gr}}(G)$, of $G$. A small modification of the definition yields the Z-Grundy domination number, which is the dual invariant of the well-known zero forcing number. In this paper, we prove that ${\gamma }_{\mathrm{gr}}(G)\ge \frac{n+\lceil \frac{k}{2}\rceil -2}{k-1}$ holds for every connected $k$-regular graph of order $n$ different from $K_{k+1}$ and $\overline{2C_4}$. The bound in the case $k=3$ reduces to ${\gamma }_{\mathrm{gr}}(G)\ge \frac{n}{2}$, and we characterize the connected cubic graphs with ${\gamma }_{\mathrm{gr}}(G)=\frac{n}{2}$. If $G$ is different from $K_4$ and $K_{3,3}$, then $\frac{n}{2}$ is also an upper bound for the zero forcing number of a connected cubic graph, and we characterize the connected cubic graphs attaining this bound.