Unbounded strong-product ratios for the Grundy domination number

Note. The counterexample of this paper was first made public on 14 October 2026, as release v1.0.0 of the repository https://github.com/creelie/grundy-strong-product, archived on Zenodo as 10.5281/zenodo.23378021. An earlier and incomplete version of the paper appeared on Hexagon on 23 October 2026 as the preprint hexagon:2610.00494, available at 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 10.5281/zenodo.23607502 and 10.5281/zenodo.23629621, in the repository 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 10.5281/zenodo.23659882 (concept 10.5281/zenodo.23607651), together with programs that recompute the small cases.

Introduction

Let $G$ be a finite simple graph and write $N[v]$ for the closed neighbourhood of a vertex $v$, the set consisting of $v$ and its neighbours. A sequence $(v_1,\ldots,v_k)$ of vertices of $G$ is legal if every $v_i$ dominates a vertex that none of its predecessors dominates, that is,

a vertex in this difference is a footprint of $v_i$.¹ The Grundy domination number $\gamma_{\mathrm{gr}}(G)$ is the length of a longest legal sequence; a longest legal sequence always dominates $G$, since otherwise an undominated vertex could be appended. The parameter was introduced by Brešar, Gologranc, Milanič, Rall and Rizzi [7], who connected it with the domination game.

In the strong product $G \boxtimes H$ two distinct vertices $(g,h)$ and $(g',h')$ are adjacent when $g' \in N_G[g]$ and $h' \in N_H[h]$; equivalently $N_{G\boxtimes H}[(g,h)] = N_G[g] \times N_H[h]$. Taking a Grundy dominating sequence of $G$ and one of $H$ and listing their pairs in lexicographic order gives a legal sequence of $G \boxtimes H$, so

for all $G$ and $H$ [6 Proposition 21].² In the same paper the authors conjectured that the bound is always attained.

The conjecture holds when $G$ is a caterpillar [6] and, more generally, when $G$ is a forest, by the work of Bell, Driscoll, Krop and Wolff [2]. A proof for all graphs was announced by Herrman and Smith [8] and later withdrawn.³ We show that the conjecture is false and that no constant multiple of its proposed value is an upper bound.

Section 2 proves this with two graphs on the five-element subsets of $\{1,\ldots,m\}$. Each factor is bounded through an incidence matrix over a finite field whose nonzero entries are exactly the closed neighbourhoods, and the diagonal of the product is an independent set. The ratio grows like $m^2$.

The smallest counterexamples we know come from a different construction, with the octahedron as first factor. For $N \ge1$ let $H_N$ be the graph on $\{0,1,\ldots,N-1\}$ in which $u$ and $v$ are adjacent when $|u-v| \equiv2 \pmod{3}$, and let $K_{2,2,2}$ be the octahedron, the complete tripartite graph with three parts of size two. We compute the Grundy domination number of $H_N$ for every order.

The proof is in § 3 to § 5. After the first vertex of a legal sequence is chosen in a suitable circulant graph containing $H_N$, the undominated vertices form a half graph, and a count at the first selected edge, or an injection at the first selected vertex of the third residue class, gives the upper bound. Explicit sequences attain it. At $N=19$ the factors have Grundy domination numbers 2 and 9, while their product has a legal sequence of length 19. This is a counterexample on 114 vertices. By Proposition 25 of [6], $\gamma_{\mathrm{gr}}(G \boxtimes H) \le|V(G)|\gamma_{\mathrm{gr}}(H)$, so with the octahedron as first factor the ratio is at most 3; Theorem 1.2 must vary both factors.

The arguments are elementary: rank bounds for matrices with prescribed support, and counting in a half graph. Counts of this kind, attached to a finite structure or a group action, also appear in the author’s earlier work [3, 4, 5].

Unbounded product ratios

To obtain unbounded ratios we vary both factors. The factor bounds come from incidence matrices over different fields, in the manner of the intersection-congruence arguments used by Alon [1, Section 3] for the Shannon capacity; the application here needs the nonzero entries to be exactly the closed neighbourhoods, so that every legal sequence, and not only every independent set, is bounded. No result about the Shannon capacity is used.

Proof. Let $(v_1,\ldots,v_k)$ be legal and choose a footprint $w_i$ for each $v_i$. The footprints are distinct, since $w_j$ is not dominated by $v_1,\ldots,v_{j-1}$ while $w_i \in N[v_i]$ for $i<j$. If $i<j$, then $w_j \notin N_G[v_i]$, so $M_{v_iw_j}=0$, and each $M_{v_iw_i}$ is nonzero. The submatrix with rows $v_1,\ldots,v_k$ and columns $w_1,\ldots,w_k$, in this order, is lower triangular with nonzero diagonal, so its rank is $k$, and $k \le\operatorname{rank} M$. $\square$

The condition on $M$ cannot be weakened to vanishing on non-edges: the footprint $w_i$ need not equal $v_i$, so the entries $M_{uv}$ with $v$ a neighbour of $u$ must be nonzero as well.⁴

Proof. Let $U$ be the incidence matrix between five-element subsets of $[m]$ and elements of $[m]$, with $U_{Sx}=1$ when $x \in S$. Over $\mathbb{F}_2$,

Since $|S|=5$ is odd, the diagonal entries are nonzero, and an off-diagonal entry is nonzero exactly when $|S \cap T|$ is odd, that is, when $S$ and $T$ are adjacent in $A_m$. So the nonzero entries of $UU^{\mathsf{T}}$ are exactly the closed neighbourhoods of $A_m$. Its rank is at most the number $m$ of columns of $U$, and Lemma 2.1 gives the first bound.

Let $V$ be the incidence matrix between five-element subsets and two-element subsets of $[m]$, with $V_{SP}=1$ when $P \subseteq S$. Over $\mathbb{F}_3$,

the number of two-element subsets of $S \cap T$. For intersection sizes $t=0,1,2,3,4,5$ the values $\binom{t}{2}=0,0,1,3,6,10$ reduce to $0,0,1,0,0,1$ modulo 3. So the entry is nonzero exactly when $S=T$ or $|S \cap T|=2$, which are precisely the closed neighbourhoods of $B_m$. The rank is at most $\binom{m}{2}$, proving the second bound.

The product vertices

form an independent set of $A_m \boxtimes B_m$: for $S \ne T$, adjacency of $(S,S)$ and $(T,T)$ would need $S$ and $T$ adjacent in both factors, which would require $|S \cap T|$ to be 1 or 3 and also 2. Listing the vertices of $D_m$ in any order gives a legal sequence, each vertex footprinting itself, because no earlier vertex of the list dominates it. This proves the lower bound $\binom{m}{5}$ for the product.

The three bounds give (2.1), since

and the right side tends to infinity with $m$. $\square$

Proof of Theorem 1.2. Take $G=A_m$ and $H=B_m$ with $m$ so large that $(m-2)(m-3)(m-4)>60Cm$.

For example, $m=13$ gives $\gamma_{\mathrm{gr}}(A_{13}\boxtimes B_{13}) \ge1287$, whereas $\gamma_{\mathrm{gr}}(A_{13})\gamma_{\mathrm{gr}}(B_{13}) \le13\cdot78=1014$. The two factor bounds use different fields; no matrix product over a common field is involved, and nothing is claimed about the exact values of $\gamma_{\mathrm{gr}}(A_m)$ and $\gamma_{\mathrm{gr}}(B_m)$.

The octahedron and the graphs $H_N$

We write the vertices of the octahedron as $g_0,g_1,g_2,x_0,x_1,x_2$, where $x_t$ is the antipode of $g_t$; the three antipodal pairs are the only non-adjacent pairs (Figure 1). Thus $N[v]$ is everything except the antipode of $v$.

Proof. The sequence $(g_0,x_0)$ is legal: $x_0$ footprints itself. Conversely, let $(u,v)$ be legal. If $v$ is the antipode of $u$, then $N[u]\cup N[v]$ is the whole vertex set; otherwise $N[u]$ misses only the antipode of $u$, which lies in $N[v]$. Either way nothing is left for a third vertex to footprint.

In $H_N$ we write $a_i=3i$, $b_i=3i+1$ and $c_i=3i+2$. Two vertices of the same residue class modulo 3 are never adjacent, and for vertices of different classes

because $c_j-a_i=3(j-i)+2$, $a_j-b_i=3(j-i)-1$ and $b_j-c_i=3(j-i)-1$, and a difference $3k-1$ with $k\le0$ has absolute value $3\lvert k\rvert+1\equiv1\pmod3$.

A long legal sequence in the product

The construction uses one property of $H_N$: with the colouring $v\mapsto v\bmod3$, every edge $uv$ with $u<v$ satisfies $u\equiv v+1\pmod3$, since $v-u\equiv2$. We state it for any graph with this property.

Proof. We show that $s_j$ footprints $f_j=(x_{t(v_j)+1},v_j)$, the indices of $g$ and $x$ being taken modulo 3. First, $f_j\in N[s_j]$: the vertex $x_{t(v_j)+1}$ is not the antipode $x_{t(v_j)}$ of $g_{t(v_j)}$, so it lies in $N[g_{t(v_j)}]$, and $v_j\in N[v_j]$. Now let $i<j$. If $f_j\in N[s_i]$, then $x_{t(v_j)+1}\in N[g_{t(v_i)}]$, which means $t(v_i)\ne t(v_j)+1$, and $v_j\in N[v_i]$, which for $i\ne j$ means that $v_iv_j$ is an edge, hence $t(v_i)=t(v_j)+1$. The two conclusions contradict each other, so $f_j\notin N[s_i]$.

Figure 2 shows the sequence for $H_{21}$. Every column of the product contains exactly one vertex of the sequence, while a sequence of the form used for (1.1) would use only $\gamma_{\mathrm{gr}}(H_{21}) = 10$ columns. The rotation of the three colours along the sequence is what lets each new vertex reach a footprint in a layer $x_t$ that none of the earlier vertices covers in that column.

The Grundy domination number of $H_N$

We prove the formula of Theorem 1.3 for every $N \ge6$. A legal sequence in an induced subgraph remains legal in the larger graph, with the same footprints, since closed neighbourhoods in the subgraph are the intersections of those in the larger graph with the subgraph. We use this observation for both bounds.

Proof. Put $n = 3q + 1$. For $1 \le d < n$, the conditions $d \equiv2 \pmod{3}$ and $n-d \equiv2 \pmod{3}$ are equivalent, because $n \equiv1$. So $u$ and $v$ are adjacent in $H_n$ exactly when $(u-v) \bmod n$ lies in the set of residues congruent to 2 modulo 3, and translation modulo $n$ preserves adjacency.⁵ A legal sequence stays legal under a graph automorphism, so we may translate a nonempty legal sequence so that its first vertex is 0.

The vertex 0 dominates itself and the vertices $C_k = 3k + 2$, $0 \le k < q$. The undominated vertices are

There are no edges within either class, and

because $X_i-Y_j = 3(i-j)+2$ when $i \ge j$, and $Y_j-X_i = 3(j-i-1)+1$ when $j > i$. Thus the undominated vertices induce a half graph with the perfect matching $X_iY_i$ (Figure 3).

Follow the sequence from its second vertex on until either a vertex $C_k$ is selected or the selected $X$- and $Y$-vertices contain an edge for the first time. Before either event, let $I$ and $J$ be the sets of selected indices on the two sides, and put $r = |I|$, $s = |J|$. By (5.1), the absence of edges means

We treat the three possibilities in turn.

A new $X_i$ creates an edge. Then $J \ne\emptyset$ and $b=\min J \le i$. All earlier $X$-indices are less than $b$ by (5), so $i$ is the largest selected $X$-index. After this step, an $X$-vertex is dominated if it was selected or if it is adjacent to a selected $Y_j$, that is, if its index is at least $b$; so the undominated $X$-indices are $\{0,\ldots,b-1\}\setminus I$. A $Y$-vertex is dominated if it was selected or is adjacent to a selected $X$-vertex, and the selected $X$-vertex with the largest index is $X_i$; so the undominated $Y$-indices are those greater than $i$ that are not in $J$. Writing $s_0=|J\cap\{b,\ldots,i\}|$ for the number of selected $Y$-indices at most $i$, the number of undominated vertices is

The number of vertices selected after 0, which is $r+s+1$, plus the number still undominated, is

because $s_0\le i-b+1$. Each later legal step dominates at least one vertex that was undominated, so the number of later steps is at most the number of undominated vertices. The full sequence, including its first vertex 0, has length at most $1+(q+1)=q+2$.

A new $Y_j$ creates an edge. The map $X_i\mapsto Y_{q-1-i}$, $Y_j\mapsto X_{q-1-j}$ exchanges the two sides and preserves (4), since $q-1-j\ge q-1-i$ exactly when $i\ge j$. It carries this case to the previous one, so again the sequence has length at most $q+2$.

A vertex $C_k$ is selected first. By (3), the neighbours of $C_k=c_k$ among the $X$- and $Y$-vertices are the $X_i=a_{i+1}$ with $i<k$ and the $Y_j=b_j$ with $j>k$. After this step every vertex still undominated belongs to

At least $r+s$ vertices of $W_k$ were dominated already before $C_k$ was selected. To see this, map each earlier selection by

Each image lies in $W_k$ and is either the selected vertex itself or its partner in the matching, which the selected vertex dominates by (4). Images of distinct selections on the same side are distinct. An image shared by a selection $X_i$ and a selection $Y_j$ would force $i=j$, with $i \in I$ and $j \in J$, contrary to (5). So the map is injective, at most $q+1-r-s$ vertices remain undominated after $C_k$, and the sequence has length at most

Neither event occurs. Then the vertices selected after $0$ form an independent set of the half graph, which has the perfect matching $X_iY_i$, so there are at most $q$ of them and the sequence has length at most $q+1$.

In every case the length is at most $q+3$.

Lemma 5.2

Lemma 5.2. If $N \ge6$ and $q=\lfloor(N+1)/3 \rfloor$, then $\gamma_{\mathrm{gr}}(H_N) \ge q+3$.

Proof. For $q=2$, the sequence $(1,3,5,0,2)$ in $H_6$ has the successive footprints $1,5,0,2,4$ and remains legal in $H_7$. For $q=3$, the sequence $(0,7,2,4,5,1)$ in $H_8$ has the successive footprints $0,7,4,6,3,1$ and remains legal in $H_9$ and $H_{10}$.⁶

For $q \ge4$ it suffices to work in $H_{3q-1}$, which is an induced subgraph of $H_N$ because $3q-1 \le N$. Its vertices are $a_i$, $b_i$ for $0 \le i \le q-1$ and $c_i$ for $0 \le i \le q-2$. Take the sequence

The first $q-2$ vertices footprint themselves, since vertices of one class are never adjacent. The last five have the successive footprints

by (3): $b_{q-1}$ is adjacent to no $a_i$ with $i \le q-3$, so it is undominated and footprints itself; $b_{q-2}$ is adjacent to $c_{q-3}$ and not to any earlier vertex of the sequence; $b_{q-3}$ is adjacent to $c_0$, because $q-3>0$, and not to $a_0,\ldots,a_{q-3}$, $b_{q-1}$ or $c_{q-3}$; neither $a_{q-2}$ nor $a_{q-1}$ is adjacent to $b_{q-1}$, $c_{q-3}$ or $c_0$, so $a_{q-2}$ footprints itself and $b_0$ footprints $a_{q-1}$. The sequence has length $(q-2)+5=q+3$.

Proof of Theorem 1.3. Put $q=\lfloor(N+1)/3 \rfloor$. Then $3q \le N+1$, so $N \le3q+1$ and $H_N$ is an induced subgraph of $H_{3q+1}$; Lemma 5.1 gives $\gamma_{\mathrm{gr}}(H_N) \le q+3$, and Lemma 5.2 gives equality. The product bound is Proposition 4.1.

At $N=19$ the formula gives $\gamma_{\mathrm{gr}}(H_{19})=9$, and $19>2\cdot9$. For $N \ge21$ write $N=3q-1$, $3q$ or $3q+1$; the differences $N-2(q+3)$ are $q-7$, $q-6$ and $q-5$, and each is positive in its range ($q \ge8$, $q \ge7$ and $q \ge7$ respectively). Hence $N>2\gamma_{\mathrm{gr}}(H_N)=\gamma_{\mathrm{gr}}(K_{2,2,2})\gamma_{\mathrm{gr}}(H_N)$ for $N=19$ and every $N \ge21$, while $\gamma_{\mathrm{gr}}(K_{2,2,2}\boxtimes H_N) \ge N$.

Example 5.3

Example 5.3. For $N=19$ the sequence (5.3) with $q=6$, in $H_{17}\subseteq H_{19}$, is $(0,3,6,9,16,11,2,12,1)$, of length $9=\gamma_{\mathrm{gr}}(H_{19})$, and $K_{2,2,2}\boxtimes H_{19}$ has 114 vertices and a legal sequence of length 19. For $N=21$, with $q=7$, the sequence is $(0,3,6,9,12,19,14,2,15,1)$, of length $10=\gamma_{\mathrm{gr}}(H_{21})$; this is the counterexample on 126 vertices with which the paper began. For $N=20$ the formula gives $\gamma_{\mathrm{gr}}(H_{20})=10$ and $20=2\cdot10$, so Theorem 1.3 says nothing about $N=20$.

A question

Declarations

Funding. None.

Conflict of interest. None.

Data availability. https://github.com/creelie/Paper_1 (release v2.0.0, archived on Zenodo as 10.5281/zenodo.23659882) holds the source of this paper and programs that recompute $\gamma_{\mathrm{gr}}(H_N)$ for small $N$ and check the sequences of Section 5; the paper does not depend on them.