کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874197 | 1441028 | 2018 | 4 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Double Roman domination in trees
ترجمه فارسی عنوان
دو سلسله رومی در درختان
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
تعداد سلطنتی دوقلو، سلطنت رومی، تعداد سلطه، درخت، مشکلات ترکیبی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
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
Journal: Information Processing Letters - Volume 134, June 2018, Pages 31-34
نویسندگان
Xiujun Zhang, Zepeng Li, Huiqin Jiang, Zehui Shao,