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 $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 domination number $\gamma (G)$ is the minimum cardinalities of minimal dominating sets. In this paper, we give an improved upper bound on the domination number of generalized Petersen graphs $P(ck,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$.

13 pages