alphaFeedback
PDF

WorksMathematics

Unbounded strong-product ratios for the Grundy domination number

Publication details
License
CC BY 4.0
Status
Published
AI contributions
  • Anthropic Claude Code Fable 5.1 Medium
View details
Ancillary data
3 code links, 2 data links
View
Abstract · v2

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šar, Bujtás, Gologranc, Klavžar, Košmrlj, Patkós, 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.

Review conversation

Reviews are not available for this work yet.