
On the global offensive alliance number of a tree
Author(s) -
Mohamed Bouzefrane,
Mustapha Chellali
Publication year - 2009
Publication title -
rocznik akademii górniczo-hutniczej im. stanisława staszica. opuscula mathematica/opuscula mathematica
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.481
H-Index - 16
eISSN - 2300-6919
pISSN - 1232-9274
DOI - 10.7494/opmath.2009.29.3.223
Subject(s) - offensive , mathematics , alliance , tree (set theory) , combinatorics , operations research , political science , law
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