20.500.12556/DKUM-66783 Open $k$-monopolies in graphs: complexity and related concepts Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open ▫$k$▫-monopolies in graphs which are closely related to different parameters in graphs. Given a graph ▫$G=(V,E)$▫ and ▫$X \subseteq V$▫, if ▫$\delta_X(v)$▫ is the number of neighbors ▫$v$▫ has in ▫$X$▫, ▫$k$▫ is an integer and ▫$t$▫ is a positive integer, then we establish in this article a connection between the following three concepts: (1) Given a nonempty set ▫$M\subseteq V$▫ a vertex ▫$v$▫ of ▫$G$▫ is said to be ▫$k$▫-controlled by ▫$M$▫ if ▫$\delta_M(v)\ge \frac{\delta_V(v)}{2}+k$▫. The set ▫$M$▫ is called an open ▫$k$▫-monopoly for ▫$G$▫ if it ▫$k$▫-controls every vertex ▫$v$▫ of ▫$G$▫. (2) A function ▫$f: V\rightarrow \{-1,1\}$▫ is called a signed total ▫$t$▫-dominating function for ▫$G$▫ if ▫$f(N(v))=\sum_{v\in N(v)}f(v)\geq t$▫ for all ▫$v\in V$▫. (3) A nonempty set ▫$S\subseteq V$▫ is a global (defensive and offensive) ▫$k$▫-alliance in ▫$G$▫ if ▫$\delta_S(v)\ge \delta_{V-S}(v)+k$▫ holds for every ▫$v\in V$▫. In this article we prove that the problem of computing the minimum cardinality of an open ▫$0$▫-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs. In addition we present some general bounds for the minimum cardinality of open ▫$k$▫-monopolies and we derive some exact values. Zaprti monopoli na grafih imajo širok nabor uporabnih aplikacij v zvezi s premagovanjem napak, saj imajo pogosto nekatere skupne pristope glede na večino, recimo problema soglasja ali diagnoze, kot tudi sistemi volitev. Tukaj predstavljamo odprte ▫$k$▫-monopole na grafih, ki so tesno povezani z nekaterimi že znanimi parametri na grafih. Naj bo ▫$G=(V,E)$▫ graf, ▫$X \subseteq V$▫, ▫$\delta_X(v)$▫ je število sosedov vozlišča ▫$v$▫ v množici ▫$X$▫, ▫$k$▫ celo in ▫$t$▫ naravno število. V članku predstavimo povezavo med naslednjimi koncepti: (1) Za neprazno množico ▫$M \subseteq V$▫ je vozlišče ▫$v\in V$▫ ▫$k$▫-kontrolirano z ▫$M$▫, če ▫$\delta_M(v)\ge \frac{\delta_V(v)}{2}+k$▫. Množici ▫$M$▫ rečemo odprti ▫$k$▫-monopol grafa ▫$G$▫, če ▫$M$▫ ▫$k$▫-kontrolira vsako vozlišče ▫$v$▫ grafa ▫$G$▫. (2) Funkcija ▫$f: V\rightarrow \{-1,1\}$▫ je predznačena totalno ▫$t$▫-dominatna funkcija grafa ▫$G$▫, če je ▫$f(N(v))=\sum_{v\in N(v)}f(v)\geq t$▫ za vsak ▫$v\in V$▫. (3) Neprazna množica ▫$S\subseteq V$▫ je globalna (obrambna in napadalna) ▫$k$▫-aliansa grafa ▫$G$▫, če ▫$\delta_S(v)\ge \delta_{V-S}(v)+k$▫ drži za vsak ▫$v\in V$▫. Prav tako pokažemo, da je problem računanja minimalne kardinalnosti odprtega ▫$0$▫-monopola v grafu NP-poln problem, tudi če se omejimo na dvodelne ali tetivne grafe. Predstavimo tudi nekatere splošne meje za minimalno kardinalnost odprtih ▫$k$▫-monopolov in določimo nekatere točne vrednosti zanje. open k-monopolies k-signed total domination global defensive k-alliance global offensive k-alliance odprti k-monopoli k-predznačena totalna dominanca globalna obrambna k-aliansa globalna napadalna k-aliansa true true true Angleški jezik Slovenski jezik Znanstveno delo 2017-07-10 11:53:12 2017-07-10 11:55:03 2022-08-01 13:09:57 2019-07-11 15:58:46 2016 0 0 str. 1-18 št. 3 Letn. 18 2016 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1365-8050 519.17 8089433 17647961 1365-8050 URN:SI:UM:DK:X7NGDC7P Discrete_Mathematics_&_Theoretical_Computer_Science_2016_Kuziak,_Peterin,_Yero_Open_k-monopolies_in_graphs_complexity_and_related_concep.pdf Discrete_Mathematics_&_Theoretical_Computer_Science_2016_Kuziak,_Peterin,_Yero_Open_k-monopolies_in_graphs_complexity_and_related_concep.pdf 1 8354A3F59916D28760F3D8758649D153 9db9849dc01bcff59ad8cd65895881f9fafde03847759843700dece5987996ed 6373bf8c-7c0e-11eb-bb7a-00155d0001ca 20.500.12556/dkum/08ef8616-564d-4616-9fda-6c077f90b39d https://dk.um.si/Dokument.php?lang=slv&id=113952 http://dmtcs.episciences.org/1407 1 https://dk.um.si/Dokument.php?lang=slv&id=113951 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0