The complexity of open k-monopolies in graphs for negative k

Abstract

Let $G$ be a graph with vertex set $V(G)$, $\delta(G)$ minimum degree of $G$ and $k\in\left\{1-\left\lceil\frac{\delta(G)}{2}\right\rceil,\ldots ,\left\lfloor \frac{\delta(G)}{2}\right\rfloor\right\}$. Given a nonempty set $M\subseteq V(G)$) a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_{M}(v) \geq \frac{\delta_{V(G)}(v)}{2}+k$ where $\delta_{M}(v)$ represents the number of neighbors of $v$ in $M$. The set $M$ is alled an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer $k$ is NP-complete even restricted to chordal graphs.