Opuscula Math. 31, no. 2 (2011), 153-158
http://dx.doi.org/10.7494/OpMath.2011.31.2.153

Opuscula Mathematica

# A note on global alliances in trees

Mohamed Bouzefrane
Mustapha Chellali

Abstract. 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.

Keywords: global defensive alliance, global offensive alliance, domination, trees.

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Mohamed Bouzefrane
• University of Blida, LAMDA-RO Laboratory, Department of Mathematics, B.P. 270, Blida, Algeria
• Mustapha Chellali
• University of Blida, LAMDA-RO Laboratory, Department of Mathematics, B.P. 270, Blida, Algeria
• Revised: 2010-08-15.
• Accepted: 2010-08-18.