| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Izpis gradiva

Naslov:Open $k$-monopolies in graphs: complexity and related concepts
Avtorji:Kuziak, Dorota (Avtor)
Peterin, Iztok (Avtor)
Yero, Ismael G. (Avtor)
Datoteke:.pdf Discrete_Mathematics_&_Theoretical_Computer_Science_2016_Kuziak,_Peterin,_Yero_Open_k-monopolies_in_graphs_complexity_and_related_concep.pdf (181,59 KB)
 
URL http://dmtcs.episciences.org/1407
 
Jezik:Angleški jezik
Vrsta gradiva:Znanstveno delo (r2)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
Opis: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.
Ključne besede:open k-monopolies, k-signed total domination, global defensive k-alliance, global offensive k-alliance
Leto izida:2016
Št. strani:str. 1-18
Številčenje:št. 3, Letn. 18
ISSN:1365-8050
UDK:519.17
COBISS_ID:17647961 Povezava se odpre v novem oknu
ISSN pri članku:1365-8050
NUK URN:URN:SI:UM:DK:X7NGDC7P
Licenca:CC BY 4.0
To delo je dosegljivo pod licenco Creative Commons Priznanje avtorstva 4.0 Mednarodna
Število ogledov:253
Število prenosov:41
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
Področja:Ostalo
:
  
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:Discrete Mathematics and Theoretical Computer Science
Skrajšan naslov:Discret. Math. Theor. Comput. Sci.
Založnik:Assoc. Discrete Math. Theor. Comput. Sci.
ISSN:1365-8050
COBISS.SI-ID:8089433 Novo okno

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:P1-0297
Naslov:Teorija grafov

Sekundarni jezik

Jezik:Slovenski jezik
Opis: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.
Ključne besede:odprti k-monopoli, k-predznačena totalna dominanca, globalna obrambna k-aliansa, globalna napadalna k-aliansa


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici