On the domination number of generalized Petersen graphs

Abstract

Let $n$ and $k$ be integers such that $3leq 2k+ 1 leq n$.The generalized Petersen graph $GP(n, k)=(V,E) $ is the graph with $V={u_1, u_2,ldots, u_n}cup{v_1, v_2,ldots, v_n}$ and $E={u_iu_{i+1}, u_iv_i, v_iv_{i+k}: 1 leq i leq n}$, whereaddition is in modulo $n$. A subset $Dsubseteq V$ is a dominating set of $GP(n, k)$ if for each $vin Vsetminus D$ there is a vertex $uin D$ adjacent to $v$. The minimum cardinality of a dominating set of $GP(n, k)$ is called the domination number of $GP(n, k)$. In this paper we give a dynamic programming algorithm for computing the domination number of a given $GP(n,k )$ in $mathcal{O}(n)$ time and space for every $k=mathcal{O}(1)$.