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.
- 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
- Received: 2010-06-15.
- Revised: 2011-02-13.
- Accepted: 2011-03-03.
