Author
Department of Mathematics, Shahrood University of Technology Shahrood, Iran
Abstract
Let $n$ and $k$ be integers such that $3\leq 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\}$, where
addition is in modulo $n$. A subset $D\subseteq V$ is a dominating set of $GP(n, k)$ if for each $v\in V\setminus D$ there is a vertex $u\in 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)$.
Keywords
)