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
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.
- J.C. Bermond, J. Bond, D. Peleg, S. Perennes, The power of small coalitions in graphs, Discrete Appl. Math. 127 (2003), 399-414.
- C. Dwork, D. Peleg, N. Pippenger, E. Upfal, Fault tolerance in networks of bounded degree, SIAM J. Comp. 17 (1988), 975-988.
- 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.
- 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.
- H. García-Molina, D. Barbara, How to assign votes in a distributed system, J. ACM 32 (1985), 841-860.
- J.H. Hattingh, M.A. Henning, P.J. Slater, The algorithmic complexity of signed domination in graphs, Australasian J. Combin. 12 (1995), 101-112.
- T.W. Haynes, S.T. Hedetniemi, M.A. Henning, Global defensive alliances in graphs, Electronic J. Combin. 10 (2003), 139-146.
- M.A. Henning, Signed total domination in graphs, Discrete Math. 278 (2004), 109-125.
- K. Khoshkhah, M. Nemati, H. Soltani, M. Zaker, A study of monopolies in graphs, Graphs Combin. 29 (2013), 1417-1427.
- D. Kuziak, I. Peterin, I.G. Yero, Computing the (\(k\)-)monopoly number of direct product of graphs, FILOMAT 29 (2015), 1163-1171.
- D. Kuziak, I. Peterin, I.G. Yero, Open \(k\)-monopolies in graphs: complexity and related concepts, Discrete Math. Comput. Sci. 18 (2016), #1407.
- 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.
- D. Kuziak, I. Peterin, I.G. Yero, Bounding the \(k\)-monopoly number of strong product graphs, Discuss. Math. Graph Theory 38 (2018), 287-299.
- H. Liang, On the signed (total) \(k\)-domination number of a graph, J. Combin. Math. Combin. Comp. 89 (2014), 87-99.
- 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.
- J. Pfaff, Algorithmic complexities of domination-related graph parameters, Ph.D. Thesis, Clemson University, Clemson, 1984.
- G.F. Sullivan, The complexity of system-level fault diagnosis and diagnosability, Ph.D. Thesis, Yale University, New Haven CT, 1986.
- 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.
- Received: 2018-01-26.
- Revised: 2018-09-18.
- Accepted: 2018-09-20.
- Published online: 2019-02-23.
