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

From papers

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

Equality conjecture.

γgrZ,k(G)=nFk(G).\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.

Progress summary

Open

The proposed exact formula remains unproved: only a one-sided bound is known, and no verified proof or counterexample has been found.

The conjecture proposes that the known lower bound is always an equality. It was stated as Conjecture 3.2 in a paper dated December 2022, which explains why the argument for k=1k=1 does not extend automatically to general kk.

Known results

  • For graphs with V(G)=n|V(G)|=n, the paper proves only γgrZ,k(G)nFk(G)\gamma_{gr}^{Z,k}(G)\ge n-F_k(G); equality is established there only as a conjecture.

Current status (as of August 2026): The lower bound γgrZ,k(G)nFk(G)\gamma_{gr}^{Z,k}(G)\ge n-F_k(G) is settled, but the equality conjecture remains open, with no verified proof, disproof, or later resolution found.

Sources
Sources & referencesView supporting material

Primary source

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

Solutions 1

Counterexample

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

Fix k2k\ge2. Let

A={u,v,a1,,ak},B={b1,,bk},A=\{u,v,a_1,\ldots,a_k\}, \qquad B=\{b_1,\ldots,b_k\},

and let GkG_k be obtained from the complete bipartite graph Kk+2,kK_{k+2,k} on ABA\sqcup B by adding the edge uvuv. Then

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

First, no singleton is a kk-forcing set. An initial vertex uu, vv, or bjb_j has more than kk white neighbors and cannot begin forcing. An initial vertex aia_i forces all kk vertices of BB, but each newly blue bjb_j then has k+1k+1 remaining white neighbors, so forcing stops.

On the other hand, start with the two blue vertices {u,a1}\{u,a_1\}. Vertex a1a_1 forces all of BB, after which any bjb_j forces the remaining kk vertices of AA. Consequently

Fk(Gk)=2.F_k(G_k)=2.

Now consider the sequence

(a1,a2,,ak,u,v,b1,b2,,bk1).(a_1,a_2,\ldots,a_k,u,v,b_1,b_2,\ldots,b_{k-1}).

This is a valid kk-ZZ-Grundy sequence:

  • For a1,,aka_1,\ldots,a_k, use the open-neighborhood witness bkb_k. The respective numbers of previous selected closed neighborhoods containing bkb_k are 0,1,,k10,1,\ldots,k-1.
  • For uu, use witness vv, which lies in zero previous selected closed neighborhoods.
  • For vv, use witness uu, which lies in one previous selected closed neighborhood.
  • For b1,,bk1b_1,\ldots,b_{k-1}, use witness a1a_1. The respective counts are 1,2,,k11,2,\ldots,k-1.

All these counts are strictly less than kk. Therefore

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

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

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

times, violating the defining strict inequality. Hence

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

It follows that

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

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

0 endorsements
Shivam Patel ·