Opuscula Math. 29, no. 3 (2009), 223-228
http://dx.doi.org/10.7494/OpMath.2009.29.3.223

Opuscula Mathematica

# On the global offensive alliance number of a tree

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 alliance if for every vertex $$v$$ in $$V-S$$, at least half of the vertices in its closed neighborhood 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)$$ is the minimum cardinality of a global offensive alliance of $$G$$. We first show that every tree of order at least three with $$l$$ leaves and $$s$$ support vertices satisfies $$\gamma_o(T) \geq (n-l+s+1)/3$$ and we characterize extremal trees attaining this lower bound. Then we give a constructive characterization of trees with equal domination and global offensive alliance numbers.

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

Mathematics Subject Classification: 05C69.

Full text (pdf)

• Mohamed Bouzefrane
• LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
• Mustapha Chellali
• LAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria
• Revised: 2009-05-01.
• Accepted: 2009-05-05.