Equality between k-Grundy Z-domination and k-forcing number
Equality between k-Grundy Z-domination and k-forcing number
Let be a graph with . The parameters and denote the -Grundy Z-domination number and the -forcing number, respectively.
Equality conjecture.
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
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 does not extend automatically to general .
Known results
- For graphs with , the paper proves only ; equality is established there only as a conjecture.
Current status (as of August 2026): The lower bound 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
Sign in to submit a solution.
The conjecture is false for EVERY , even for connected graphs satisfying its minimum-degree hypothesis.
Fix . Let
and let be obtained from the complete bipartite graph on by adding the edge . Then
First, no singleton is a -forcing set. An initial vertex , , or has more than white neighbors and cannot begin forcing. An initial vertex forces all vertices of , but each newly blue then has remaining white neighbors, so forcing stops.
On the other hand, start with the two blue vertices . Vertex forces all of , after which any forces the remaining vertices of . Consequently
Now consider the sequence
This is a valid --Grundy sequence:
- For , use the open-neighborhood witness . The respective numbers of previous selected closed neighborhoods containing are .
- For , use witness , which lies in zero previous selected closed neighborhoods.
- For , use witness , which lies in one previous selected closed neighborhood.
- For , use witness . The respective counts are .
All these counts are strictly less than . Therefore
A sequence containing all vertices is impossible. At its final step, for every possible open-neighborhood witness of the final vertex, the previous selected closed neighborhoods contain exactly
times, violating the defining strict inequality. Hence
It follows that
Already for , the graph has six vertices and gives . Thus the asserted equality fails for every forcing parameter .