← Back to arXiv
arXivCombinatoricsarXiv:2607.19412

A correction to the Zero Forcing Number of the Generalized Petersen Graphs $P(n,3)$

The paper deals with a concept called "zero forcing" on graphs. A graph is a collection of dots (vertices) connected by lines (edges). Zero forcing is a process where you start by coloring some vertices blue and then repeatedly apply a rule: if a blue vertex has exactly one non-blue neighbor, that neighbor gets colored blue too. The "zero forcing number" of a graph is the smallest set of initially blue vertices that eventually forces the entire graph to turn blue. This number has connections to problems in linear algebra and network theory, making it worth calculating precisely for well-known graph families.

The graphs in question are called generalized Petersen graphs, written P(n,3). These are a family of symmetric, well-structured graphs built from two concentric rings of vertices connected in a specific pattern. A 2020 published paper claimed that the zero forcing number of P(n,3) equals 8 for all sufficiently large n, specifically for n at least 12. The new paper shows this claim is wrong for n = 12, where seven initial vertices are actually enough to force the whole graph. The authors back this up by exhibiting an explicit seven-vertex starting set and tracing through every step of the forcing process, and they also confirmed by exhaustive computer search that six vertices are not sufficient.

Beyond correcting the specific error, the authors use computer searches to calculate the exact zero forcing number for all P(n,3) graphs with n between 7 and 20, and they pinpoint where the original proof went wrong: it failed to rule out certain seven-vertex configurations in its case analysis. They also prove that the zero forcing number is at most 8 for all n of 9 or greater, using a single explicit construction and the symmetry of the graphs. Based on all of this, they conjecture that the corrected statement should be that the zero forcing number equals 8 for n of 13 or greater, but acknowledge that proving a matching lower bound for all large n remains an open problem.

Read original →