کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419799 | 683861 | 2009 | 6 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Offensive rr-alliances in graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Offensive rr-alliances in graphs Offensive rr-alliances in graphs](/preview/png/419799.png)
چکیده انگلیسی
Let G=(V,E)G=(V,E) be a simple graph. For a nonempty set X⊂VX⊂V, and a vertex v∈V,δX(v)v∈V,δX(v) denotes the number of neighbors vv has in XX. A nonempty set S⊂VS⊂V is an offensive rr-alliance in GG if δS(v)≥δS̄(v)+r,∀v∈∂(S), where ∂(S)∂(S) denotes the boundary of SS. An offensive rr-alliance SS is called global if it forms a dominating set. The global offensive rr-alliance number of GG, denoted by γro(G), is the minimum cardinality of a global offensive rr-alliance in GG. We show that the problem of finding optimal (global) offensive rr-alliances is NP-complete and we obtain several tight bounds on γro(G).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 1, 6 January 2009, Pages 177–182
Journal: Discrete Applied Mathematics - Volume 157, Issue 1, 6 January 2009, Pages 177–182
نویسندگان
Henning Fernau, Juan A. Rodríguez, José M. Sigarreta,