کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650541 1342492 2008 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
αα-Domination perfect trees
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
αα-Domination perfect trees
چکیده انگلیسی

Let α∈(0,1)α∈(0,1) and let G=(VG,EG)G=(VG,EG) be a graph. According to Dunbar et al. [αα-Domination, Discrete Math. 211 (2000) 11–26], a set D⊆VGD⊆VG is an αα-dominating set of G   if |NG(u)∩D|⩾αdG(u)|NG(u)∩D|⩾αdG(u) for all u∈VG⧹Du∈VG⧹D. Similarly, we define a set D⊆VGD⊆VG to be an αα-independent set of G   if |NG(u)∩D|⩽αdG(u)|NG(u)∩D|⩽αdG(u) for all u∈Du∈D. The αα-domination number γα(G)γα(G) of G   is the minimum cardinality of an αα-dominating set of G   and the αα-independent αα-domination number iα(G)iα(G) of G   is the minimum cardinality of an αα-dominating set of G   that is also αα-independent. A graph G   is αα-domination perfect if γα(H)=iα(H)γα(H)=iα(H) for all induced subgraphs H of G.We characterize the αα-domination perfect trees in terms of their minimally forbidden induced subtrees. For α∈(0,12] there is exactly one such tree whereas for α∈(12,1) there are infinitely many.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3187–3198
نویسندگان
, , ,