کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650541 | 1342492 | 2008 | 12 صفحه PDF | دانلود رایگان |
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.
Journal: Discrete Mathematics - Volume 308, Issue 15, 6 August 2008, Pages 3187–3198