Lighting Up a Graph: the surprise hiding in $P(12,3)$

Sunday, July 12, 2026 Math

Let $G = (V,E)$ be a finite simple graph, $S \subseteq V$ colored black, $V \setminus S$ white.

Color change rule. A black vertex with exactly one white neighbor forces that neighbor black.

Iterating until no force remains gives the closure $\mathrm{cl}(S)$. $S$ is a zero forcing set if $\mathrm{cl}(S) = V$, and $Z(G)$, the zero forcing number, is the minimum size of one. (Origin: minimum rank of graph-patterned symmetric matrices; irrelevant below.)

The graph: $P(n,k)$

The generalized Petersen graph $P(n,k)$ has vertex set

outer cycle $u_i \sim u_{i+1}$, spokes $u_i \sim v_i$, inner edges $v_i \sim v_{i+k}$, indices mod $n$; $3$-regular on $2n$ vertices. $P(5,2)$ is the classic Petersen graph. Below, $P(12,3)$; click a vertex to toggle it.

$Z(P(12,3)) = 7$

Rashidi, Shajareh Poursalavati, and Tavakkoli (2020) claim $Z(P(n,3)) = 8$ for all $n \ge 12$. This is false at $n=12$: $Z(P(12,3)) = 7$, witnessed by $S = \{u_0,\dots,u_6\}$.

Indices mod $12$.

Round 1. $i=1,\dots,5$: $u_i$ has black neighbors $u_{i-1},u_{i+1}$, white neighbor $v_i$, so $u_i \to v_i$. ($u_0,u_6$: two white neighbors, no force.)

Round 2.

($v_3$: inner neighbors $v_0,v_6$ both white, no force.)

Round 3. $v_7,v_8,v_{10},v_{11}$ have both inner neighbors black, so force their spokes: $v_7 \to u_7$, $v_8 \to u_8$, $v_{10}\to u_{10}$, $v_{11}\to u_{11}$.

Round 4. $u_0 \to v_0$, $u_6 \to v_6$, $u_8 \to u_9$.

Round 5. $v_6 \to v_9$, the last white vertex.

$24$ of $24$ black, so $Z(P(12,3)) \le 7$. Lower bound: $\binom{24}{6} = 134{,}596$ six-vertex subsets, exhaustive search (two independent implementations), none forces. Hence

$Z(P(n,3))$ is not monotone

Every entry exhaustive. $8$ at $n=10$, $7$ at $n=11,12$, $8$ from $n=13$ on — a two-value dip.

$\{u_0,\dots,u_6\}$ forces $P(11,3)$ and $P(12,3)$, no other $P(n,3)$ for $10 \le n \le 300$ (verified computationally). On $P(13,3)$:

One extra vertex around the ring and the skip-by-three edges no longer close up; the process halts with a ring of survivors.

$Z(P(n,3)) \le 8$ for all $n \ge 9$

No computer needed here — the eight-vertex witness plus symmetry.

Two facts about $\mathrm{cl}$, immediate from the rule: monotonicity ($A \subseteq B \implies \mathrm{cl}(A) \subseteq \mathrm{cl}(B)$) and equivariance ($\mathrm{cl}(\varphi(A)) = \varphi(\mathrm{cl}(A))$ for automorphism $\varphi$). The rotation $\rho: u_i \mapsto u_{i+1}, v_i \mapsto v_{i+1} \pmod n$ is an automorphism of $P(n,3)$. Let $S = \{u_0,\dots,u_7\}$.

Step 1: $u_8 \in \mathrm{cl}(S)$. $u_i \to v_i$ for $i=1,\dots,6$; then $v_4 \to v_7$; then $u_7 \to u_8$. All indices in $\{0,\dots,8\}$, distinct mod $n$ for $n \ge 9$, so each step holds as written.

Step 2: $\mathrm{cl}(S)$ is $\rho$-invariant. $\rho(S) = \{u_1,\dots,u_8\} \subseteq \mathrm{cl}(S)$, so $\rho(\mathrm{cl}(S)) = \mathrm{cl}(\rho(S)) \subseteq \mathrm{cl}(\mathrm{cl}(S)) = \mathrm{cl}(S)$; $\rho$ a bijection on a finite set gives equality.

Step 3: $\mathrm{cl}(S) = V$. $\mathrm{cl}(S) \ni u_0$ and is $\rho$-invariant, and $\rho$‘s orbit of $u_0$ is the whole outer cycle, so every $u_i \in \mathrm{cl}(S)$. A white $v_i$ would be $u_i$‘s sole white neighbor, forcing it — contradiction. So $\mathrm{cl}(S) = V$.

What’s open

Exhaustive search gives $Z(P(n,3))$ for $7 \le n \le 20$, stabilizing at $8$ from $n=13$, conjecturally

Upper bound: proved above, unconditionally. Lower bound: checked only through $n=20$. The $n=11,12$ dip is the reason not to trust extrapolation here — it’s exactly the kind of accident a finite table would hide. Closing the gap means excluding every seven-vertex forcing set uniformly in $n$, not computing further.

Zero forcing lab.