Article ID Journal Published Year Pages File Type
4650541 Discrete Mathematics 2008 12 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,