Algorithmic and complexity aspects of computing Roman {2}-domination in graphs
سال انتشار: 1398
نوع سند: مقاله کنفرانسی
زبان: انگلیسی
مشاهده: 429
فایل این مقاله در 6 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICIORS12_094
تاریخ نمایه سازی: 24 شهریور 1398
چکیده مقاله:
Let G (V,E) be a graph. A Roman {2}-dominating function (R2DF) } 2, 1, 0{ : Vf on G has the property that for every vertex Vv i ith 0 v feither there is ) (v Nu i ith 2) ( uf or there are ) ( , v N y x i ith 1) ( ) ( y f x f . The i eight of a R2DF f is equal to v V v f f w Theminimum i eight of a R2DF on G is the Roman {2}- domination number of G . In this paper, i e first shoi that the associated decisionproblem for Roman {2}-domination is NP-complete even i hen restricted to chordal and planar graphs. Then, i e give a linear algorithm that computes the Roman {2}-domination number of a given tree
کلیدواژه ها:
نویسندگان
Abolfazl Poureidi
Faculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, Iran