Browsing by Subject "k-domination number"

Now showing 1 - 2 of 2

Access status: Restricted ,
Liczby wielokrotnie dominujące graf
(Data obrony: 2012-09-27) Dziewońska, Marta
Wydział Matematyki Stosowanej
Access status: Open Access ,
Trees with equal global offensive k-alliance and k-domination numbers
(2010) Chellali, Mustapha
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)$.