کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902736 | 1632242 | 2018 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Client-server and cost effective sets in graphs
ترجمه فارسی عنوان
سرور مشتری و مقرون به صرفه مجموعه در نمودار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
For any integer kâ¥0, a set of vertices S of a graph G=(V,E) is k-cost-effective if for every vâS,|N(v)â©(VâS)|â¥|N(v)â©S|+k. In this paper we study the minimum cardinality of a maximal k-cost-effective set and the maximum cardinality of a k-cost-effective set. We obtain Gallai-type results involving the k-cost-effective and global k-offensive alliance parameters, and we provide bounds on the maximum k-cost-effective number. Finally, we consider k-cost-effective sets that are also dominating. We show that computing the k-cost-effective domination number is NP-complete for bipartite graphs. Moreover, we note that not all trees have a k-cost-effective dominating set and give a constructive characterization of those that do.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 15, Issue 2, August 2018, Pages 211-218
Journal: AKCE International Journal of Graphs and Combinatorics - Volume 15, Issue 2, August 2018, Pages 211-218
نویسندگان
Mustapha Chellali, Teresa W. Haynes, Stephen T. Hedetniemi,