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].
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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)) = ∑u∈V(G) f(u). An RDF f can be represented as f = (V0, V1, V2), where Vi = {v ∈ V : f(v) = i} for i = 0, 1, 2. An RDF f = (V0, V1, V2) is called a locating Roman dominating function (or just LRDF) if N(u) ∩ V2 ≠ N(v) ∩ V2 for any pair u, v of distinct vertices of V0. The locating Roman domination number [...] γRL(G) $\gamma _R^L (G)$ is the minimum weight of an LRDF of G. In this paper, we study the locating Roman domination number in trees. We obtain lower and upper bounds for the locating Roman domination number of a tree in terms of its order and the number of leaves and support vertices, and characterize trees achieving equality for the bounds.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on G. Note that the 1-distance Roman domination number γ1R (G) is the usual Roman domination number γR(G). In this paper, we investigate properties of the k-distance Roman domination number. In particular, we prove that for any connected graph G of order n ≥ k +2, γkR (G) ≤ 4n/(2k +3) and we characterize all graphs that achieve this bound. Some of our results extend these ones given by Cockayne et al. in 2004 and Chambers et al. in 2009 for the Roman domination number.
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ć.