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 2 / 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. The counterexample of this paper was first made public on 14 October 2026, as release \texttt{v1.0.0} of the repository \url{https://github.com/creelie/grundy-strong-product}, archived on Zenodo as \href{https://doi.org/10.5281/zenodo.23378021}{10.5281/zenodo.23378021}. An earlier and incomplete version of the paper appeared on Hexagon on 23 October 2026 as the preprint \texttt{hexagon:2610.00494}, available at \url{https://hexagonmath.org/2610.00494}. That version gave one counterexample, the strong product of the octahedron with the graph $H_{21}$ on $21$ vertices, and relied on a computer certificate for the Grundy domination number of $H_{21}$. The revisions that followed are archived on Zenodo as \href{https://doi.org/10.5281/zenodo.23607502}{10.5281/zenodo.23607502} and \href{https://doi.org/10.5281/zenodo.23629621}{10.5281/zenodo.23629621}, in the repository \url{https://github.com/creelie/Paper_1}. This version is complete and self-contained: the Grundy domination number of $H_N$ is computed by hand for every $N\ge6$, the ratio is shown to be unbounded, the scope of each result is stated, no statement rests on a computer, and the only unrefereed source it depends on is the withdrawn proof claim that it mentions for the record. The source of this revision is in the repository named in the data availability statement at the end, archived on Zenodo as \href{https://doi.org/10.5281/zenodo.23659882}{10.5281/zenodo.23659882} (concept \href{https://doi.org/10.5281/zenodo.23607651}{10.5281/zenodo.23607651}), together with programs that recompute the small cases.

Tools used

Anthropic
Claude CodeVersion Fable 5.1 Medium

References

  1. N. Alon, The Shannon capacity of a union, Combinatorica 18 (1998), no. 3, 301--310. doi:10.1007/PL00009824 (https://doi.org/10.1007/PL00009824).DOI
  2. K. Bell, K. Driscoll, E. Krop and K. Wolff, Grundy domination of forests and the strong product conjecture, Electron. J. Combin. 28 (2021), no. 2, Paper P2.12. doi:10.37236/9507 (https://doi.org/10.37236/9507).DOI
  3. D. Bhattacharjee, Establishing equivariant class [O][O] for hyperbolic groups, Asian Res. J. Math. 18 (2022), no. 11, 362--369. doi:10.9734/arjom/2022/v18i11615 (https://doi.org/10.9734/arjom/2022/v18i11615).DOI
  4. D. Bhattacharjee, Non-commutativity over canonical suspension η\eta for genus g≥1g\ge1 in hypercomplex structures for potential ρϕ\rho\phi, Asian Res. J. Math. 18 (2022), no. 11, 332--341. doi:10.9734/arjom/2022/v18i11607 (https://doi.org/10.9734/arjom/2022/v18i11607).DOI
  5. D. Bhattacharjee, U. Bhattacharya, Iterated nerve complexes for kk-fold sensor coverage, Preprints.org (2026). doi:10.20944/preprints202606.1351.v2 (https://doi.org/10.20944/preprints202606.1351.v2).DOI
  6. 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 (2016), no. 4, Paper P4.34. doi:10.37236/6269 (https://doi.org/10.37236/6269).DOI
  7. B. Brešar, T. Gologranc, M. Milanič, D. F. Rall and R. Rizzi, Dominating sequences in graphs, Discrete Math. 336 (2014), 22--36. doi:10.1016/j.disc.2014.07.016 (https://doi.org/10.1016/j.disc.2014.07.016).DOI
  8. R. Herrman and S. G. Z. Smith, A proof of the Grundy domination strong product conjecture, arXiv:2212.04565 (https://arxiv.org/abs/2212.04565v2) (2022), withdrawn in version 2 (12 January 2023).arXiv

Version history

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