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)\leq2\gamma(T)-1$ and if $n\geq3,$ then $\gamma_{o}(T)\leq\frac{3}{2}\gamma_{a}(T)-1$. Moreover, all extremal trees attaining the first bound are characterized.
Uitgever:
AGH University of Science and Technology (provided by DOAJ)
Tijdschrift beschrijving