Equality between k-Grundy Z-domination and k-forcing number

At least 3 years old · documented by 2022

Let $G=(V,E)$ be a graph with $|V(G)|=n$ . The parameters $\gamma_{gr}^{Z,k}(G)$ and $F_k(G)$ denote the $k$ -Grundy Z-domination number and the $k$ -forcing number, respectively.

Equality conjecture.

\gamma_{gr}^{Z,k}(G)=n-F_k(G).

This conjecture would show that the lower bound established in the preceding theorem is always sharp. The supplied text gives no evidence that the conjecture has been resolved.

References

Primary source

Rebekah Herrman and Stephen G. Z. Smith, “Extending Grundy domination to k-Grundy domination”, arXiv:2212.09861 (2022).

Posted 1 month ago

Progress summary

Refreshed 1 month ago

Claimed solved

An unverified posted construction claims the conjecture is false for every forcing parameter at least two, while the published work proves only the corresponding lower bound.

Herrman and Smith proposed the equality in 2022 after proving a one-sided bound. They noted that the argument establishing equality when the parameter is one does not extend automatically to general parameters.

Known results

Herrman and Smith (2022): for every graph, $\gamma_{\mathrm{gr}}^{Z,k}(G)\ge n-F_k(G)$ .
Herrman and Smith (2022): equality is stated as Conjecture 3.2, not proved in general; the paper gives exact values for some graph families.

Posted attempt

A posted construction claims a connected graph $G_k$ for every $k\ge2$ with $|V(G_k)|=2k+2$ , $F_k(G_k)=2$ , and $\gamma_{\mathrm{gr}}^{Z,k}(G_k)=2k+1$ , contradicting the conjectured value $n-F_k(G_k)=2k$ . The construction is a claimed complete disproof, but it has not been independently verified.

Current status (as of August 2026): The lower bound $\gamma_{\mathrm{gr}}^{Z,k}(G)\ge n-F_k(G)$ is settled, while a posted construction claims to disprove equality for every $k\ge2$ and the conjecture remains mathematically unverified.

Sources

CounterexampleThis solution needs a summarySee full solutionHide full solution

The conjecture is false for EVERY $k\ge2$ , even for connected graphs satisfying its minimum-degree hypothesis.

Fix $k\ge2$ . Let

A=\{u,v,a_1,\ldots,a_k\}, \qquad B=\{b_1,\ldots,b_k\},

and let $G_k$ be obtained from the complete bipartite graph $K_{k+2,k}$ on $A\sqcup B$ by adding the edge $uv$ . Then

|V(G_k)|=2k+2,\qquad \delta(G_k)=k.

First, no singleton is a $k$ -forcing set. An initial vertex $u$ , $v$ , or $b_j$ has more than $k$ white neighbors and cannot begin forcing. An initial vertex $a_i$ forces all $k$ vertices of $B$ , but each newly blue $b_j$ then has $k+1$ remaining white neighbors, so forcing stops.

On the other hand, start with the two blue vertices $\{u,a_1\}$ . Vertex $a_1$ forces all of $B$ , after which any $b_j$ forces the remaining $k$ vertices of $A$ . Consequently

F_k(G_k)=2.

Now consider the sequence

(a_1,a_2,\ldots,a_k,u,v,b_1,b_2,\ldots,b_{k-1}).

This is a valid $k$ - $Z$ -Grundy sequence:

For $a_1,\ldots,a_k$ , use the open-neighborhood witness $b_k$ . The respective numbers of previous selected closed neighborhoods containing $b_k$ are $0,1,\ldots,k-1$ .
For $u$ , use witness $v$ , which lies in zero previous selected closed neighborhoods.
For $v$ , use witness $u$ , which lies in one previous selected closed neighborhood.
For $b_1,\ldots,b_{k-1}$ , use witness $a_1$ . The respective counts are $1,2,\ldots,k-1$ .

All these counts are strictly less than $k$ . Therefore

\gamma_{\mathrm{gr}}^{Z,k}(G_k)\ge2k+1.

A sequence containing all $2k+2$ vertices is impossible. At its final step, for every possible open-neighborhood witness $w$ of the final vertex, the previous selected closed neighborhoods contain $w$ exactly

\deg(w)\ge\delta(G_k)=k

times, violating the defining strict inequality. Hence

\gamma_{\mathrm{gr}}^{Z,k}(G_k)=2k+1.

It follows that

\boxed{ \gamma_{\mathrm{gr}}^{Z,k}(G_k) =2k+1 > 2k =|V(G_k)|-F_k(G_k) } \qquad(k\ge2).

Already for $k=2$ , the graph has six vertices and gives $5\ne6-2=4$ . Thus the asserted equality fails for every forcing parameter $k\ge2$ .