Opuscula Math. 29, no. 3 (2009), 223-228

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)

Opuscula Mathematica - cover

Cite this article as:
Mohamed Bouzefrane, Mustapha Chellali, On the global offensive alliance number of a tree, Opuscula Math. 29, no. 3 (2009), 223-228, http://dx.doi.org/10.7494/OpMath.2009.29.3.223

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.