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

Mustapha Chellali

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.

Full text (pdf)