کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872603 | 684166 | 2012 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Global defensive alliances of trees and Cartesian product of paths and cycles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
Given a graph G, a defensive alliance of G is a set of vertices SâV(G) satisfying the condition that for each vâS, at least half of the vertices in the closed neighborhood of v are in S. A defensive alliance S is called global if every vertex in V(G)âS is adjacent to at least one member of the defensive alliance S. The global defensive alliance number of G, denoted γa(G), is the minimum size around all the global defensive alliances of G. In this paper, we present an efficient algorithm to determine the global defensive alliance numbers of trees, and further give formulas to decide the global defensive alliance numbers of complete k-ary trees for k=2,3,4. We also establish upper bounds and lower bounds for γa(PmÃPn),γa(CmÃPn) and γa(CmÃCn), and show that the bounds are sharp for certain m,n.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 4â5, March 2012, Pages 479-487
Journal: Discrete Applied Mathematics - Volume 160, Issues 4â5, March 2012, Pages 479-487
نویسندگان
Chan-Wei Chang, Ma-Lian Chia, Cheng-Ju Hsu, David Kuo, Li-Ling Lai, Fu-Hsing Wang,