Loading...
Please wait, while we are loading the content...
Similar Documents
Offensive k-alliances in graphs
| Content Provider | Semantic Scholar |
|---|---|
| Author | Fernau, Henning RodrÃguez, Jairo Arbey Sigarreta, Jose Maria |
| Copyright Year | 2007 |
| Abstract | 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)$. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://arxiv.org/pdf/math/0703598v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
