Offensive k-alliances in graphs

Details Offensive k-alliances in graphs Offensive k-alliances in graphs

2007-03-20

arxiv.org/abs/math/0703598v1

Discrete Applied Mathematics 157 (1) (2009) 177-182

Mathematics

Combinatorics

Scientific paper

Let $G=(V,E)$ be a simple graph. For a nonempty set $X\subset V,$ and a vertex $v\in V,$ $\delta_{X}(v)$ denotes the number of neighbors $v$ has in $X.$ A nonempty set $S\subset V$ is an \emph{offensive $r$-alliance} in $G$ if $\delta_S(v)\ge \delta_{\bar{S}}(v)+r,$ $\forall v\in \partial (S),$ where $\partial (S)$ denotes the boundary of $S$. An offensive $r$-alliance $S$ is called \emph{global} if it forms a dominating set. The \emph{global offensive $r$-alliance number} of $G$, denoted by $\gamma_{r}^{o}(G)$, is the minimum cardinality of a global offensive $r$-alliance in $G$. We show that the problem of finding optimal (global) offensive $r$-alliances is NP-complete and we obtain several tight bounds on $\gamma_{r}^{o}(G)$.

Affiliated with

Also associated with

No associations

Rating

Offensive k-alliances in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Offensive k-alliances in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Offensive k-alliances in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-123542