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

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)\).

Abstract licence: CC BY

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.