On the domination number of generalized Petersen graphs

	On the domination number of generalized Petersen graphs
Journal of Algorithms and Computation
دوره 52، شماره 2، اسفند 2020، صفحه 57-65 اصل مقاله (278.97 K)
شناسه دیجیتال (DOI): 10.22059/jac.2020.79236
نویسنده
Abolfazl Poureidi^*
Department of Mathematics, Shahrood University of Technology Shahrood, Iran
چکیده
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)$.
کلیدواژه‌ها
Dominating set؛ Algorithm؛ Dynamic programming؛ Generalized Petersen graph

آمار تعداد مشاهده مقاله: 170 تعداد دریافت فایل اصل مقاله: 221

سامانه مدیریت نشریات علمی. قدرت گرفته از سیناوب