A linear-time algorithm to compute total $[1,2]$-domination number of block graphs

	A linear-time algorithm to compute total $[1,2]$-domination number of block graphs
AUT Journal of Mathematics and Computing
مقاله 12، دوره 1، شماره 2، آذر 2020، صفحه 263-270 اصل مقاله (431.19 K)
نوع مقاله: Original Article
شناسه دیجیتال (DOI): 10.22060/ajmc.2020.18444.1035
نویسندگان
Pouyeh Sharifani¹^{، 2}؛ Mohammadreza Hooshmandasl^* ³^{، 2}؛ Saeid Alikhani⁴
¹Institute for Research in Fundamental Sciences (IPM), Tehran, Iran
²Department of Computer Science, Yazd University, Yazd, Iran
³Department of Computer Science, University of Mohaghegh Ardabili, Ardabil, Iran
⁴Department of Mathematics, Yazd University, Yazd, Iran
چکیده
Let $G=(V, E)$ be a simple graph without isolated vertices. A set $D\subseteq V$ is a total $[1,2]$-dominating set if for every vertex $v\in V , 1\leq \|N(v)\cap D\|\leq 2$. The total $[1,2]$-domination problem is to determine the total $[1,2]$-domination number $\gamma_{t[1,2]}(G)$, which is the minimum cardinality of a total $[1,2]$-dominating set for a graph $G$. In this paper, we present a linear-time algorithm to compute $\gamma_{t[1,2]}(G)$, for a block graph $G$.
کلیدواژه‌ها
Total $[1,2]$-set؛ Dominating set؛ Block graph
مراجع

آمار تعداد مشاهده مقاله: 1,633 تعداد دریافت فایل اصل مقاله: 940