HEXAGONbeta

Unbounded strong-product ratios for the Grundy domination number

A mix of human-written and AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Deep Bhattacharjee

Version 1 / Oct 23, 2026 / CC BY 4.0

Abstract

A sequence of vertices of a graph is legal when every vertex in it dominates some vertex that none of the earlier ones dominated, and the Grundy domination number of the graph is the length of its longest legal sequence. In the strong product of two graphs, two vertices are adjacent when each coordinate is equal or adjacent in its factor. It has been known since 2016 that the Grundy domination number of a strong product is at least the product of the Grundy domination numbers of the two factors, and it was conjectured, by Bre\v{s}ar, Bujt\'as, Gologranc, Klav\v{z}ar, Ko\v{s}mrlj, Patk\'os, Tuza and Vizer, that equality always holds. We show that the conjecture is false, and false by an unbounded factor: for every number CC there are graphs whose strong product has Grundy domination number more than CC times the product of the two factors. The graphs are built on the five-element subsets of an mm-element set, with adjacency decided by the size of the intersection; incidence matrices over the fields with two and three elements bound the two factors by mm and (m2)\binom m2, while the diagonal of the product is an independent set of size (m5)\binom m5. We also compute the Grundy domination number of the graph on {0,…,N−1}\{0,\dots,N-1\} in which uu and vv are adjacent when ∣u−v∣≡2(mod3)|u-v|\equiv2\pmod3: it is ⌊(N+1)/3⌋+3\lfloor(N+1)/3\rfloor+3 for every N≥6N\ge6. Its strong product with the octahedron has a legal sequence of length NN, so the conjecture already fails for N=19N=19, on a graph with 114114 vertices, and for every N≥21N\ge21. Every statement is proved by hand.

Provenance statement

Deep Bhattacharjee chose the problem and directed the work. Claude (Anthropic), through Claude Code, carried out the searches and computations, wrote the checking programs and the Lean 4 proofs and drafted the paper. Refutes Conjecture 22 of Brešar et al. The proofs are written out in the paper; the programs and their outputs are in the release. The author approved the final version. Code and data: release v1.0.0, https://github.com/creelie/grundy-strong-product/releases/tag/v1.0.0.
AI provenance filesAI-PROVENANCE-HEXAGON.md · 1 KB

Tools used

Anthropic
Claude CodeVersion Fable 5.1 Medium

References

  1. D. Bhattacharjee, The Grundy domination number is not multiplicative on strong products: Lean 4 development, programs and data , version 1.0.0, Zenodo, 2026. 10.5281/zenodo.23378021; https://github.com/creelie/grundy-strong-productDOI
  2. K. Bell, K. Driscoll, E. Krop and K. Wolff, Grundy domination of forests and the strong product conjecture , Electron. J. Combin. 28 (2) (2021), #P2.12. 10.37236/9507DOI
  3. B. Brešar, Cs. Bujtás, T. Gologranc, S. Klavžar, G. Košmrlj, B. Patkós, Zs. Tuza and M. Vizer, Dominating sequences in grid-like and toroidal graphs , Electron. J. Combin. 23 (4) (2016), #P4.34. 10.37236/6269DOI
  4. B. Brešar, T. Gologranc, M. Milanič, D. F. Rall and R. Rizzi, Dominating sequences in graphs , Discrete Math. 336 (2014), 22--36. 10.1016/j.disc.2014.07.016DOI
  5. R. Herrman and S. G. Z. Smith, A proof of the Grundy domination strong product conjecture , arXiv:2212.04565, 2022 (withdrawn). https://arxiv.org/abs/2212.04565arXiv
  6. L. de Moura and S. Ullrich, The Lean 4 theorem prover and programming language , in: Automated Deduction -- CADE 28, Lecture Notes in Comput. Sci., Springer, Cham, 2021, pp. 625--635. 10.1007/978-3-030-79876-5_37DOI

Version history

  1. v1Submitted by Deep BhattacharjeeInitial depositSupersededOct 23, 2026
  2. v2Submitted by Deep BhattacharjeeSubmitted as a new versionCurrentOct 26, 2026