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

Opuscula Mathematica

# Global offensive k-alliance in bipartite graphs

Mustapha Chellali
Lutz Volkmann

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.

Full text (pdf)

• Mustapha Chellali
• University of Blida, LAMDA-RO Laboratory, Department of Mathematics, B.P. 270, Blida, Algeria
• Lutz Volkmann
• RWTH Aachen University, Lehrstuhl II für Mathematik, Templergraben 55, D-52056 Aachen, Germany
• Revised: 2011-02-13.
• Accepted: 2011-03-03.