Opuscula Math. 32, no. 1 (), 83-89
http://dx.doi.org/10.7494/OpMath.2012.32.1.83
Opuscula Mathematica

# Global offensive k-alliance in bipartite graphs

Abstract. Let $$k \geq 0$$ be an integer. A set $$S$$ of vertices of a graph $$G=(V(G),E(G))$$ is called a global offensive $$k$$-alliance if $$|N(v) \cap S| \geq |N(v) \cap S|+k$$ for every $$v \in V(G)-S$$, where $$0 \leq k \leq \Delta$$ and $$\Delta$$ is the maximum degree of $$G$$. The global offensive $$k$$-alliance number $$\gamma^k_o(G)$$ is the minimum cardinality of a global offensive $$k$$-alliance in $$G$$. We show that for every bipartite graph $$G$$ and every integer $$k \geq 2$$, $$\gamma^k_o(G) \leq \frac{n(G)+|L_k(G)|}{2}$$, where $$L_k(G)$$ is the set of vertices of degree at most $$k-1$$. Moreover, extremal trees attaining this upper bound are characterized.
Keywords: global offensive $$k$$-alliance number, bipartite graphs, trees.
Mathematics Subject Classification: 05C69.