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)$.
Poureidi, A. (2020). On the domination number of generalized Petersen graphs. Journal of Algorithms and Computation, 52(2), 57-65. doi: 10.22059/jac.2020.79236
MLA
Abolfazl Poureidi. "On the domination number of generalized Petersen graphs". Journal of Algorithms and Computation, 52, 2, 2020, 57-65. doi: 10.22059/jac.2020.79236
HARVARD
Poureidi, A. (2020). 'On the domination number of generalized Petersen graphs', Journal of Algorithms and Computation, 52(2), pp. 57-65. doi: 10.22059/jac.2020.79236
VANCOUVER
Poureidi, A. On the domination number of generalized Petersen graphs. Journal of Algorithms and Computation, 2020; 52(2): 57-65. doi: 10.22059/jac.2020.79236
)