TY  - JOUR
ID  - Peterin2019
LB  - Peterin2019
AU  - Peterin, Iztok
TI  - The complexity of open k-monopolies in graphs for negative k
ST  - The complexity of open k-monopolies in graphs for negative k
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2019
VL  - 39
IS  - 3
SP  - 425
EP  - 431
DO  - https://doi.org/10.7494/OpMath.2019.39.3.425
UR  - https://doi.org/10.7494/OpMath.2019.39.3.425
AB  - 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)\ge\frac{\delta_{V(G)}(v)}{2}+k\) where \(\delta_M(v)\) represents the number of neighbors of \(v\) in \(M\). The set \(M\) is called 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.
KW  - open \(k\)-monopolies
KW  - complexity
KW  - total domination
SN  - 1232-9274
ER  -