The Grundy domination number is not multiplicative on strong products

Introduction

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

a vertex in this difference is a footprint of $v_i$. The vertices of a legal sequence are distinct. The Grundy domination number $\gamma_{\mathrm{gr}}(G)$ is the length of a longest legal sequence; a longest legal sequence always dominates $G$. The parameter was introduced by Brešar, Gologranc, Milanič, Rall and Rizzi [4], 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$ [3 Proposition 21]. In the same paper the authors conjectured that the bound is always attained.

The conjecture holds when $G$ is a caterpillar [3] 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 [5] and later withdrawn.¹ We show that the conjecture is false.

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}$. Let $K_{2,2,2}$ be the octahedron, the complete tripartite graph with three parts of size two.

The lower bound for the product is a short explicit argument valid for every $N$ (Proposition 3.1), and so is $\gamma_{\mathrm{gr}}(K_{2,2,2})=2$ (Lemma 2.1). The upper bound $\gamma_{\mathrm{gr}}(H_{21})\le10$ is the one step that rests on a finite computation: an exhaustive search through the sets dominated by legal sequences, which we have certified in the Lean 4 proof assistant [6] (§ 4). The same search gives a family of counterexamples.

The second statement of Theorem 1.3 is computational (§ 5); the first is Proposition 3.1. If the formula for $\gamma_{\mathrm{gr}}(H_N)$ holds for all $N$, the ratio approaches $3/2$. By Proposition 25 of [3], $\gamma_{\mathrm{gr}}(G\boxtimes H)\le|V(G)|\gamma_{\mathrm{gr}}(H)$, so for $G=K_{2,2,2}$ the ratio can never exceed 3.

The graphs

We write the vertices of the octahedron as $g_0,g_1,g_2,x_0,x_1,x_2$ (in this order, $0,\ldots,5$), where $x_i$ is the antipode of $g_i$; 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 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$. When $N=3n$ the graph has a circular description (Figure 2). Recall that the circular clique $K_{p/q}$ has vertex set $\mathbb{Z}_p$, two vertices being adjacent when their cyclic distance is at least $q$.

Proof. Give $a_i$, $c_i$ and $b_i$ the positions $i$, $n+i$ and $2n+i$ modulo $3n$. Vertices of the same class are at cyclic distance at most $n-1$ and are not adjacent. For two vertices of different classes, name them so that the second follows the first in the cyclic order $A \to C \to B \to A$ of the blocks: the pairs are $(a_i,c_j)$, $(c_i,b_j)$ and $(b_i,a_j)$. In each case the second position minus the first is $n+(j-i)$ modulo $3n$, with $|j-i| \le n-1$, so the cyclic distance is at least $n+1$ when $j>i$, exactly $n$ when $j=i$, and at most $n-1$ when $j<i$. Comparing with (2): the pair is adjacent exactly when $j>i$, except that $a_i \sim c_i$.

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$. 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)$, indices of $g$ and $x$ 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_i v_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]$. $\square$

Figure 3 shows the sequence for $H_{21}$. Every column of the product contains exactly one vertex of the sequence, while a Grundy dominating sequence of the form used for (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_{21}$

Proof. The sequence $(a_0,a_1,a_2,a_3,a_4,b_6,c_4,c_0,a_5,b_0)$, that is $(0,3,6,9,12,19,14,2,15,1)$, is legal and dominating. By (2), $a_0$ dominates $c_0,\ldots,c_6$; each $a_i$ with $1\le i\le4$ footprints itself and $b_{i-1}$; then $b_6$ footprints itself, $c_4$ footprints $b_5$, $c_0$ footprints $b_4$, $a_5$ footprints itself and $b_0$ footprints $a_6$. $\square$

For the upper bound we use the sets of dominated vertices. For a legal sequence $S=(v_1,\ldots,v_k)$ put $D(S)=N[v_1]\cup\cdots\cup N[v_k]$. Define families $\mathcal{L}_0,\mathcal{L}_1,\ldots$ of vertex sets by $\mathcal{L}_0=\{\varnothing\}$ and

Proof. Induction on $k$: if $(v_1,\ldots,v_{k+1})$ is legal, then $D=D(v_1,\ldots,v_k)\in\mathcal{L}_k$ and $N[v_{k+1}]\not\subseteq D$, so $D\cup N[v_{k+1}]\in\mathcal{L}_{k+1}$. Conversely, every member of $\mathcal{L}_k$ is $D(S)$ for a legal sequence $S$ of length $k$, by the same induction.

The families can be large in general, but for $H_{21}$ they are small: by (2), the vertices of a class dominated by the vertices of another class form an initial or a final segment of that class.² Their sizes are

and $\mathcal{L}_{11}=\varnothing$; the only member of $\mathcal{L}_{10}$ is the whole vertex set. With Lemma 4.2 this gives the following.

We have verified Proposition 4.3 in three independent ways. In Lean 4, a certificate lists the 5479 sets of the families $\mathcal{L}_0,\ldots,\mathcal{L}_{10}$ as bit masks stored in binary search trees, and the kernel checks by evaluation that $\varnothing\in\mathcal{L}_0$, that $D\cup N[v]\in\mathcal{L}_{k+1}$ for every $D\in\mathcal{L}_k$ and every $v$ with $N[v]\not\subseteq D$, and that no member of $\mathcal{L}_{10}$ has a proper extension. A formal version of Lemma 4.2, proved in Lean for every graph and every such certificate, then bounds the length of every legal sequence of $H_{21}$ by 10. The Lean statement uses the definitions of legal sequences, of $H_{21}$, of $K_{2,2,2}$ and of the strong product given in this paper, and the main theorem strong_product_counterexample: there is a dominating legal sequence of length 21 in $K_{2,2,2} \boxtimes H_{21}$, every legal sequence of $K_{2,2,2}$ has length at most 2, every legal sequence of $H_{21}$ has length at most 10, and $2 \cdot10 < 21$ depends only on the standard axioms propext and Quot.sound; no native_decide is used. Independently, a C program computes the families by breadth-first search, and a Python program finds $\gamma_{\mathrm{gr}}(H_{21}) = 10$ by a memoised depth-first search over dominated sets; both use only the definition of $H_{21}$.

Proof of Theorem 1.2. Lemma 2.1, Lemma 4.1 with Proposition 4.3, and Proposition 3.1 with $N = 21$. □

The family $H_N$

The same breadth-first search, run for $6 \le N \le63$, gives the values in Table 1; for $N \le24$ they agree with the depth-first search. With Proposition 3.1 this proves Theorem 1.3.³ The largest search, for $N = 63$, visits 193 131 321 dominated sets and takes about five minutes on one core. The upper bound for $N = 21$ is the only one we have checked in Lean.

$N$	6–7	8–10	11–13	14–16	17–19	20–22	23–25	26–28	29–31	$\cdots$	59–61	62–63
$\gamma_{\mathrm{gr}}(H_N)$	5	6	7	8	9	10	11	12	13	$\cdots$	23	24

Remark 5.3. Deleting the matching $\{a_i c_i\}$ from $H_{3n}$ leaves the circular clique $K^{3n/(n+1)}$ (Proposition 2.2), a circulant graph, and it still satisfies the hypothesis of Proposition 3.1. Our search gives $\gamma_{\mathrm{gr}}(K^{3n/(n+1)}) = n + 4$ for $3 \le n \le11$, one more than $\gamma_{\mathrm{gr}}(H_{3n})$. Hence $K_{2,2,2} \boxtimes K_{27/10}$, $K_{2,2,2} \boxtimes K_{30/11}$ and $K_{2,2,2} \boxtimes K_{33/12}$ are counterexamples as well, with a vertex-transitive second factor; the matching only makes the counterexamples smaller.

Computations and formal verification

The Lean development, the C and Python programs, their outputs and the scripts that rebuild this paper are in the archive [1]. The Lean files (Lean 4.34.1, no external libraries) contain 25 theorems; all of them depend only on the standard axioms.

Use of generative AI

The author used Claude (Anthropic) to check the results by computer and in Lean and to help draft the text; the author verified every step and is responsible for the content.