Opuscula Math. 39, no. 3 (2019), 425-431
https://doi.org/10.7494/OpMath.2019.39.3.425

Opuscula Mathematica

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

Iztok Peterin

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)\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.

Keywords: open $$k$$-monopolies, complexity, total domination.

Mathematics Subject Classification: 05C85, 05C69, 05C07.

Full text (pdf)

1. J.C. Bermond, J. Bond, D. Peleg, S. Perennes, The power of small coalitions in graphs, Discrete Appl. Math. 127 (2003), 399-414.
2. C. Dwork, D. Peleg, N. Pippenger, E. Upfal, Fault tolerance in networks of bounded degree, SIAM J. Comp. 17 (1988), 975-988.
3. O. Favaron, G. Fricke, W. Goddard, S.M. Hedetniemi, S.T. Hedetniemi, P. Kristiansen, R.C. Laskar, R.D. Skaggs, Offensive alliances in graphs, Discuss. Math. Graph Theory 24 (2004), 263-275.
4. H. Fernau, J.A. Rodríguez-Velázquez, A survey on alliances and related parameters in graphs, Electronic J. Graph Theory Appl. 2 (2014), 70-86.
5. H. García-Molina, D. Barbara, How to assign votes in a distributed system, J. ACM 32 (1985), 841-860.
6. J.H. Hattingh, M.A. Henning, P.J. Slater, The algorithmic complexity of signed domination in graphs, Australasian J. Combin. 12 (1995), 101-112.
7. T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Global defensive alliances in graphs, Electronic J. Combin. 10 (2003), 139-146.
8. M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), 109-125.
9. K. Khoshkhah, M. Nemati, H. Soltani, M. Zaker, A study of monopolies in graphs, Graphs Combin. 29 (2013), 1417-1427.
10. D. Kuziak, I. Peterin, I.G. Yero, Computing the ($$k$$-)monopoly number of direct product of graphs, FILOMAT 29 (2015), 1163-1171.
11. D. Kuziak, I. Peterin, I.G. Yero, Open $$k$$-monopolies in graphs: complexity and related concepts, Discrete Math. Comput. Sci. 18 (2016), #1407.
12. D. Kuziak, I. Peterin, I.G. Yero, On the ($$k$$-)monopolies of lexicographic product graphs: bounds and closed formulas, Bull. Math. Soc. Sci. Math. Roumanie 59 (2016), 355-366.
13. D. Kuziak, I. Peterin, I.G. Yero, Bounding the $$k$$-monopoly number of strong product graphs, Discuss. Math. Graph Theory 38 (2018), 287-299.
14. H. Liang, On the signed (total) $$k$$-domination number of a graph, J. Combin. Math. Combin. Comp. 89 (2014), 87-99.
15. N. Linial, D. Peleg, Y. Rabinovich, M. Saks, Sphere packing and local majorities in graphs, 2nd Israel Symposium on Theory and Computing Systems (1993), 141-149.
16. J. Pfaff, Algorithmic complexities of domination-related graph parameters, Ph.D. Thesis, Clemson University, Clemson, 1984.
17. G.F. Sullivan, The complexity of system-level fault diagnosis and diagnosability, Ph.D. Thesis, Yale University, New Haven CT, 1986.
18. B. Zelinka, Signed total domination number of a graph, Czechoslovak Math. J. 51 (2001), 225-229.
• Iztok Peterin
• https://orcid.org/0000-0002-1990-6967
• University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška 46, 2000 Maribor, Slovenia
• Institute of Mathematics, Physics, and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
• Communicated by Mirko Horňák.
• Revised: 2018-09-18.
• Accepted: 2018-09-20.
• Published online: 2019-02-23.