On computing total double Roman domination number of trees in linear time

	On computing total double Roman domination number of trees in linear time
Journal of Algorithms and Computation
دوره 52، شماره 1، شهریور 2020، صفحه 131-137 اصل مقاله (236.1 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22059/jac.2020.76537
نویسنده
Abolfazl Poureidi^*
Department of Mathematics, Shahrood University of Technology Shahrood, Iran
چکیده
Let $G=(V,E)$ be a graph. A double Roman dominating function (DRDF) on $G$ is a function $f:V\to\{0,1,2,3\}$ such that for every vertex $v\in V$ if $f(v)=0$, then either there is a vertex $u$ adjacent to $v$ with $f(u)=3$ or there are vertices $x$ and $y$ adjacent to $v$ with $f(x)=f(y)=2$ and if $f(v)=1$, then there is a vertex $u$ adjacent to $v$ with $f(u)\geq2$. A DRDF $f$ on $G$ is a total DRDF (TDRDF) if for any $v\in V$ with $f(v)>0$ there is a vertex $u$ adjacent to $v$ with $f(u)>0$. The weight of $f$ is the sum $f(V)=\sum_{v\in V}f (v)$. The minimum weight of a TDRDF on $G$ is the total double Roman domination number of $G$. In this paper, we give a linear algorithm to compute the total double Roman domination number of a given tree.
کلیدواژه‌ها
Total double Roman dominating function؛ linear algorithm؛ Dynamic programming؛ Combinatorial optimization؛ Tree

آمار تعداد مشاهده مقاله: 298 تعداد دریافت فایل اصل مقاله: 230

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