TY  - JOUR
ID  - Bouzefrane2011
LB  - Bouzefrane2011
AU  - Bouzefrane, Mohamed
AU  - Chellali, Mustapha
TI  - A note on global alliances in trees
ST  - A note on global alliances in trees
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2011
VL  - 31
IS  - 2
SP  - 153
EP  - 158
DO  - http://dx.doi.org/10.7494/OpMath.2011.31.2.153
UR  - http://dx.doi.org/10.7494/OpMath.2011.31.2.153
AB  - For a graph \(G=(V,E)\), a set \(S\subseteq V\) is a dominating set if every vertex in \(V-S\) has at least a neighbor in \(S\). A dominating set \(S\) is a global offensive (respectively, defensive) alliance if for each vertex in \(V-S\) (respectively, in \(S\)) at least half the vertices from the closed neighborhood of \(v\) are in \(S\). The domination number \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\), and the global offensive alliance number \(\gamma_{o}(G)\) (respectively, global defensive alliance number \(\gamma_{a}(G)\)) is the minimum cardinality of a global offensive alliance (respectively, global deffensive alliance) of \(G\). We show that if \(T\) is a tree of order \(n\), then \(\gamma_{o}(T)\leq 2\gamma(T)-1\) and if \(n\geq 3\), then \(\gamma_{o}(T)\leq \frac{3}{2}\gamma_{a}(T)-1\). Moreover, all extremal trees attaining the first bound are characterized.
KW  - global defensive alliance
KW  - global offensive alliance
KW  - domination
KW  - trees
SN  - 1232-9274
ER  -