Opuscula Math. 30, no. 3 (), 249-254
http://dx.doi.org/10.7494/OpMath.2010.30.3.249
Opuscula Mathematica

# Trees with equal global offensive k-alliance and k-domination numbers

Abstract. Let $$k \geq 1$$ 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) - S| + k$$ for every $$v \in V(G)- S$$, where $$N(v)$$ is the neighborhood of $$v$$. The subset $$S$$ is a $$k$$-dominating set of $$G$$ if every vertex in $$V(G) - S$$ has at least $$k$$ neighbors in $$S$$. The global offensive $$k$$-alliance number $$\gamma_0^k (G)$$ is the minimum cardinality of a global offensive $$k$$-alliance in $$G$$ and the $$k$$-domination number $$\gamma _k (G)$$ is the minimum cardinality of a $$k$$-dominating set of $$G$$. For every integer $$k \geq 1$$ every graph $$G$$ satisfies $$\gamma_0^k (G) \geq \gamma_k (G)$$. In this paper we provide for $$k \geq 2$$ a characterization of trees $$T$$ with equal $$\gamma_0^k (T)$$ and $$\gamma_k (T)$$.
Keywords: global offensive $$k$$-alliance number, $$k$$-domination number, trees.
Mathematics Subject Classification: 05C69.