| Title: | Open $k$-monopolies in graphs: complexity and related concepts |
|---|
| Authors: | ID Kuziak, Dorota (Author)
ID Peterin, Iztok (Author)
ID Yero, Ismael G. (Author) |
|---|
| Files: |  Discrete_Mathematics_&_Theoretical_Computer_Science_2016_Kuziak,_Peterin,_Yero_Open_k-monopolies_in_graphs_complexity_and_related_concep.pdf (181,59 KB)
MD5: 8354A3F59916D28760F3D8758649D153
PID: 20.500.12556/dkum/08ef8616-564d-4616-9fda-6c077f90b39d
 http://dmtcs.episciences.org/1407
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| Abstract: | 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. |
|---|
| Keywords: | open k-monopolies, k-signed total domination, global defensive k-alliance, global offensive k-alliance |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Year of publishing: | 2016 |
|---|
| Number of pages: | str. 1-18 |
|---|
| Numbering: | Letn. 18, št. 3 |
|---|
| PID: | 20.500.12556/DKUM-66783  |
|---|
| ISSN: | 1365-8050 |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1365-8050 |
|---|
| COBISS.SI-ID: | 17647961 |
|---|
| NUK URN: | URN:SI:UM:DK:X7NGDC7P |
|---|
| Publication date in DKUM: | 10.07.2017 |
|---|
| Views: | 1263 |
|---|
| Downloads: | 187 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
