کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6874197 1441028 2018 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Double Roman domination in trees
ترجمه فارسی عنوان
دو سلسله رومی در درختان
کلمات کلیدی
تعداد سلطنتی دوقلو، سلطنت رومی، تعداد سلطه، درخت، مشکلات ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A double Roman dominating function on a graph G is a function f:V(G)→{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=3 or two vertices v1 and v2 for which f(v1)=f(v2)=2, and every vertex u for which f(u)=1 is adjacent to at least one vertex v for which f(v)≥2. The weight of a double Roman dominating function f is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a double Roman dominating function on a graph G is called the double Roman domination numberγdR(G) of G. Beeler et al. (2016) [6] showed that 2γ(G)≤γdR(G)≤3γ(G) and showed that 2γ(T)+1≤γdR(T)≤3γ(T) for any non-trivial tree T and posed a problem that if it is possible to construct a polynomial algorithm for computing the value of γdR(T) for any tree T. In this paper, we answer this problem by giving a linear time algorithm to compute the value of γdR(T) for any tree T. Moreover, we give characterizations of trees with 2γ(T)+1=γdR(T) and γdR(T)+1=2γR(T).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 134, June 2018, Pages 31-34
نویسندگان
, , , ,