Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 2

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
EN
A subset D of the vertex set V of a graph G is called an [1, k]-dominating set if every vertex from V — D is adjacent to at least one vertex and at most fc vertices of D. A [1, k]-dominating set with the minimum number of vertices is called a [formula]-set and the number of its vertices is the [1, k]-domination number [formula] of G. In this short note we show that the decision problem whether [formula] is an NP-hard problem, even for bipartite graphs. Also, a simple construction of a bipartite graph G of order n satisfying [formula] is given for every integer n ≥ (k + l)(2k + 3).
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.