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

• Autorzy: Peterin Iztok

Identyfikatory

DOI

10.7494/OpMath.2019.39.3.425

• Języki publikacji: EN

Abstrakty

EN

Let G be a graph with vertex set V(G), δ (G) minimum degree of G and [formula]. Given a nonempty set M ⊆ V(G) a vertex v of G is said to be k-controlled by M if [formula] where δM(v) represents the number of neighbors of v in M. The set M is called an open k-monopoly for G if it fc-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.

Słowa kluczowe

EN

open k-monopolies; complexity; total domination

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 3
• Strony: 425--431
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Peterin Iztok

• University of Maribor Faculty of Electrical Engineering and Computer Science Koroska 46, 2000 Maribor, Slovenia Institute of Mathematics, Physics, and Mechanics Jadranska 19, 1000 Ljubljana, Slovenia

Bibliografia

• [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. Rodriguez-Velazquez, A survey on alliances and related parameters in graphs, Electronic J. Graph Theory Appl. 2 (2014), 70-86.
• [5] H. Garcia-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. Liniał, 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.