@article {
author = {Poureidi, Abolfazl},
title = {On the domination number of generalized Petersen graphs},
journal = {Journal of Algorithms and Computation},
volume = {52},
number = {2},
pages = {57-65},
year = {2020},
publisher = {University of Tehran},
issn = {2476-2776},
eissn = {2476-2784},
doi = {10.22059/jac.2020.79236},
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\}$, whereaddition 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 = {Dominating set,Algorithm,Dynamic Programming,Generalized Petersen graph},
url = {https://jac.ut.ac.ir/article_79236.html},
eprint = {https://jac.ut.ac.ir/article_79236_83169ff58aaf301dce65ecd29d8d6030.pdf}
}