Grundy domination and zero forcing in regular graphs (Q2238998)

Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). For \(u\in V(G)\), let \(N(u)=\{w\in V(G):uw\in E(G)\}\) and \(N[u]=N(u) \cup\{u\}\). Let \(C_n\), \(K_n\) and \(K_{\alpha, n-\alpha}\), respectively, denote the cycle, the complete graph and the complete bi-partite graph (with parts of size \(\alpha\) and \(n-\alpha\)) of order \(n\). We denote by \(\overline{G}\) the complement of \(G\). The Grundy domination number \(\gamma_{\mathrm{gr}}(G)\) of \(G\) is the maximum \(x\) such that a sequence \((v_1, v_2, \ldots, v_{x})\) of distinct vertices of length \(x\) in \(G\) satisfies \(N[v_i]\setminus(\bigcup_{j=1}^{i-1}N[v_j]) \neq \emptyset\) for each \(i\in\{2,\ldots,x\}\). For \(k\ge 3\) and for any connected \(k\)-regular graph \(G\) of order \(n\) with \(G\not\in\{K_{k+1}, \overline{2C_4}\}\), the authors show that \(\gamma_{\mathrm{gr}}(G)\ge \frac{n+\lceil\frac{k}{2}\rceil-2}{k-1}\) and they characterize connected 3-regular graphs achieving equality. The zero forcing number \(Z(G)\) of \(G\) is the minimum cardinality of initial sets \(S\) of blue vertices (whereas vertices in \(V(G) \setminus S\) are colored white) such that \(V(G)\) is turned blue after finitely many applications of ``the color-change rule'': a white vertex is converted blue if it is the only white neighbor of a blue vertex. \textit{M. Gentner} and \textit{D. Rautenbach} [Discrete Appl. Math. 236, 203--213 (2018; Zbl 1377.05058)] showed that, for any connected graph \(G\) of order \(n\) and maximum degree \(\Delta \ge 3\) with \(G\not\in\{K_{\Delta+1}, K_{\Delta, \Delta}, K_{\Delta-1, \Delta},H_1, H_2\}\), where \(H_1\) and \(H_2\) are two specific graphs of orders \(5\) and \(7\), \(Z(G) \le \frac{(\Delta-2)n}{\Delta-1}\); notice that, if \(G\) is a connected 3-regular graph of order \(n\) with \(G\not\in\{K_{4}, K_{3,3}\}\), then \(Z(G)\le \frac{n}{2}\). The Z-Grundy domination number \(\gamma_{\mathrm{gr}}^Z(G)\) of \(G\) is the maximum \(x\) such that a sequence \((v_1, v_2, \ldots, v_{x})\) of distinct vertices of length \(x\) in \(G\) satisfies \(N(v_i)\setminus(\bigcup_{j=1}^{i-1}N[v_j]) \neq \emptyset\) for each \(i\in\{2,\ldots, x\}\). \textit{B. Brešar} et al. [Discrete Optim. 26, 66--77 (2017; Zbl 1387.05177)] showed that, for any graph \(G\) without isolated vertices, \(Z(G)+\gamma_{\mathrm{gr}}^Z(G)=|V(G)|\). This, together with the result of Gentner and Rautenbach [loc. cit.] implies that, for any connected \(3\)-regular graph of order \(n\) with \(G\not\in\{K_{4}, K_{3,3}\}\), \(\gamma_{\mathrm{gr}}^Z(G) \ge \frac{n}{2}\). The authors of this paper characterize connected \(3\)-regular graphs \(G\) of order \(n\) satisfying \(\gamma_{\mathrm{gr}}^Z(G)=\frac{n}{2}\) (and thus \(Z(G)=\frac{n}{2}\)). For \(k\ge 3\) and for any connected \(k\)-regular graph \(G\) of order \(n\) with \(G\neq K_{k+1}\), the authors also obtain some lower bounds of \(\gamma_{\mathrm{gr}}^Z(G)\) in terms of \(n\) and \(k\).