Computing the zero forcing number for generalized Petersen graphs

Abstract

Let $G$ be a simple undirected graph with each vertex colored either white or black, $u$ be a black vertex of $G$, and exactly one neighbor $v$ of $u$ be white. Then change the color of $v$ to black. When this rule is applied, we say $u$ forces $v$, and write $u \to v$. A zero forcing set of a graph $G$ is a subset $Z$ of vertices such that if initially the vertices in $Z$ are colored black and remaining vertices are colored white, the entire graph $G$ may be colored black by repeatedly applying the color-change rule. The zero forcing number of $G$, denoted $Z(G)$, is the minimum size of a zero forcing set. In this paper, we investigate the zero forcing number for the generalized Petersen graphs (It is denoted by $P(n,k)$). We obtain upper and lower bounds for the zero forcing number for $P(n,k)$. We show that $Z(P(n,2))=6$ for $n\geq 10$, $Z(P(n,3))=8$ for $n\geq 12$ and $Z(P(2k+1,k))=6$ for $k\geq 5$.

Received: 9 July 2018 | Accepted: 10 October 2019