Opuscula Math. 39, no. 3 (2019), 425-431

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
  • ORCID iD 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.
Opuscula Mathematica - cover

Cite this article as:
Iztok Peterin, The complexity of open k-monopolies in graphs for negative k, Opuscula Math. 39, no. 3 (2019), 425-431, https://doi.org/10.7494/OpMath.2019.39.3.425

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.