Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 4

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
1
Content available remote

On the Complexity of Reinforcement in Graphs

100%
Rad N. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 4
877-887
EN
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
2
Content available remote

Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees

63%
Chellali M., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
337-346
EN
A Roman dominating function (RDF) on a graph G = (V,E) is a function f : V −→ {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).
3
Content available remote

On The Roman Domination Stable Graphs

63%
Hajian M., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2017
|
tom 37
|
nr 4
859-871
EN
A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {0, 1, 2} satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under removal of any vertex. In this paper we present upper bounds for the Roman domination number in the class of Roman domination stable graphs, improving bounds posed in [V. Samodivkin, Roman domination in graphs: the class RUV R, Discrete Math. Algorithms Appl. 8 (2016) 1650049].
4
Content available remote

Various Bounds for Liar’s Domination Number

51%
Alimadadi A., Mojdeh D. A., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2016
|
tom 36
|
nr 3
629-641
EN
Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V (G) can be correctly identified as an intruder location under these restrictions. The minimum cardinality of a liar’s dominating set is called the liar’s domination number, and is denoted by γLR(G). In this paper, we present sharp bounds for the liar’s domination number in terms of the diameter, the girth and clique covering number of a graph. We present two Nordhaus-Gaddum type relations for γLR(G), and study liar’s dominating set sensitivity versus edge-connectivity. We also present various bounds for the liar’s domination component number, that is, the maximum number of components over all minimum liar’s dominating sets.
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ć.