| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava

Iskanje po katalogu digitalne knjižnice Pomoč

Iskalni niz: išči po
išči po
išči po
išči po
* po starem in bolonjskem študiju

Opcije:
  Ponastavi


1 - 2 / 2
Na začetekNa prejšnjo stran1Na naslednjo stranNa konec
1.
Efficient open domination in graph products
Dorota Kuziak, Iztok Peterin, Ismael G. Yero, 2014, izvirni znanstveni članek

Opis: A graph ▫$G$▫ is an efficient open domination graph if there exists a subset ▫$D$▫ of ▫$V(G)$▫ for which the open neighborhoods centered in vertices of ▫$D$▫ form a partition of ▫$V(G)$▫. We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the Cartesian product we give a characterization when one factor is ▫$K_2$▫.
Ključne besede: graph theory, efficient open domination, graph products, total domination
Objavljeno: 10.07.2017; Ogledov: 259; Prenosov: 40
.pdf Celotno besedilo (804,78 KB)
Gradivo ima več datotek! Več...

2.
Open $k$-monopolies in graphs: complexity and related concepts
Dorota Kuziak, Iztok Peterin, Ismael G. Yero, 2016, izvirni znanstveni članek

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
Objavljeno: 10.07.2017; Ogledov: 252; Prenosov: 41
.pdf Celotno besedilo (181,59 KB)
Gradivo ima več datotek! Več...

Iskanje izvedeno v 0.05 sek.
Na vrh
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici