On the Domination Number of Generalized Petersen Graphs $P(ck,k)$

Abstract

Let $G=(V(G),E(G))$ be a simple, connected, and undirected graph with vertex set $V(G)$ and edge set $E(G)$. A set $S\subseteq V(G)$ is a \emph{dominating set} if for each $v\in V(G)$, either $v\in S$ or $v$ is adjacent to some $w\in S$. That is, $S$ is a dominating set if and only if $N[S]=V(G)$. The \emph{domination number} $\gamma (G)$ is the minimum cardinality of minimal dominating sets. In this paper, we provide an improved upper bound on the domination number of generalized Petersen graphs $P(c,k)$ for $c\ge 3$ and $k\ge 3$. We also prove that $\gamma (P(4k,k))=2k+1$ for even $k$, $\gamma (P(5k,k))=3k$ for all $k\ge 1$, and $\gamma (P(6k,k))=\lceil \frac{10k}{3}\rceil$ for $k\ge 1$ and $k\ne 2$.