Search

An outer independent (double) Roman dominating function is a (double) Roman dominating function f for which the set of vertices assigned 0 under f is independent. The outer independent (double) Roman domination number ( γ oidR (G) ) γ oiR (G) is the minimum weight taken over all outer independent (double) Roman dominating functions of G. A vertex cover number β (G) is the minimum size of any vertex cover sets of a graph G. In this work, we present some contributions to the study of outer independent double Roman domination in graphs. Characterizations of the families of all connected graphs with small outer independent double Roman domination numbers, and tight lower and upper bounds on this parameter are given. We also prove that the decision problem associated with γ oidR (G) is NP-complete even when restricted to planar graphs with maximum degree at most four. We moreover prove that 2 β (T) + 1 ≤ γ oidR (T) ≤ 3 β (T) for any tree T, and show that each integer between the lower and upper bounds is realizable. Finally, we give an exact formula for this parameter concerning the corona graphs. [ABSTRACT FROM AUTHOR]

A Roman dominating function (RD-function) 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. An Roman dominating function f in a graph G is perfect Roman dominating function (PRD-function) if every vertex u with f(u) = 0 is adjacent to exactly one vertex v for which f(v) = 2. The (perfect) Roman domination number γR(G) (γpR(G) γ R p (G) $ {\gamma }_R^p(G)$) is the minimum weight of an (perfect) Roman dominating function on G. We say that γpR(G) γ R p (G) $ {\gamma }_R^p(G)$ strongly equals γR(G), denoted by γpR(G) ≡ γR(G) γ R p (G) ≡ γ R (G) $ {\gamma }_R^p(G)\equiv {\gamma }_R(G)$ , if every RD-function on G of minimum weight is a PRD-function. In this paper we show that for a given graph G, it is NP-hard to decide whether γpR(G) = γR(G) γ R p (G) = γ R (G) $ {\gamma }_R^p(G)={\gamma }_R(G)$ and also we provide a constructive characterization of trees T with γpR(T) ≡ γR(T) γ R p (T) ≡ γ R (T) $ {\gamma }_R^p(T)\equiv {\gamma }_R(T)$. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer and G be a simple and finite graph with vertex set V (G). A signed total Roman k -dominating function (STR k DF) on a graph G is a function f : V (G) → { − 1 , 1 , 2 } such that (i) every vertex v with f (v) = − 1 is adjacent to at least one vertex u with f (u) = 2 and (ii)  ∑ u ∈ N (v) f (u) ≥ k holds for any vertex v. The weight of an STR k DF f is ∑ u ∈ V (G) f (u) , and the minimum weight of an STR k DF is the signed total Roman k -domination number γ stR k (G) of G. In this paper, we establish some sharp bounds on the signed total Roman 2-domination number. [ABSTRACT FROM AUTHOR]

Let k ≥ 1 be an integer and G be a simple and finite graph with vertex set V(G). A signed double Roman k-dominating function (SDRkDF) on a graph G is a function f:V(G) → {−1,1,2,3} such that (i) every vertex v with f(v) = −1 is adjacent to at least two vertices assigned a 2 or to at least one vertex w with f(w) = 3, (ii) every vertex v with f(v) = 1 is adjacent to at least one vertex w with f(w) ≥ 2 and (iii) ∑u∈N[v]f(u) ≥ k holds for any vertex v. The weight of a SDRkDF f is ∑u∈V(G)f(u), and the minimum weight of a SDRkDF is the signed double Roman k-domination number γksdR(G) γ sdR k (G) $ {\gamma }_{{sdR}}^k(G)$ of G. In this paper, we investigate the signed double Roman k-domination number of trees. In particular, we present lower and upper bounds on γksdR(T) γ sdR k (T) $ {\gamma }_{{sdR}}^k(T)$ for 2 ≤ k ≤ 6 and classify all extremal trees. [ABSTRACT FROM AUTHOR]

A Roman {2}-dominating function (R{2}DF) 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 either at least one vertex v with f(v) = 2 or two vertices v1, v2 with f(v1) = f(v2) = 1. The weight of an R{2}DF f is the value w(f) = ∑u∈Vf(u). The minimum weight of an R{2}DF on a graph G is called the Roman {2}-domination number γ{R2}(G) of G. An R{2}DF f is called an independent Roman {2}-dominating function (IR{2}DF) if the set of vertices with positive weight under f is independent. The minimum weight of an IR{2}DF on a graph G is called the independent Roman {2}-domination number i{R2}(G) of G. In this paper, we answer two questions posed by Rahmouni and Chellali. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , an independent Roman dominating function (IRDF) is a function f : V → { 0 , 1 , 2 } having the property that: (1) every vertex assigned a value of 0 is adjacent to at least one vertex assigned a value of 2, (2) there are no two adjacent vertices with positive assignments. The weight of an IRDF ( w (f) ) is the sum of assignments for all vertices. The minimum weight of an independent Roman dominating function on graph G is the independent Roman domination number, denoted by i R (G) . In this paper, we prove that the decision problem of minimum IRDF is N P -complete for chordal bipartite graphs. Then, we research the difference in complexity between the decision problem of RDF and IRDF. Finally, we propose a linear-time algorithm for computing the minimum weight of an independent Roman dominating function in trees. [ABSTRACT FROM AUTHOR]

A double Roman dominating function on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } with the properties that if f (u) = 0 , then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if f (u) = 1 , then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w (f) = ∑ v ∈ V f (v) . The double Roman domination number γ d R (G) of a graph G is the minimum weight of a double Roman dominating function of G. A graph is said to be double Roman if γ d R (G) = 3 γ (G) , where γ (G) is the domination number of G. We obtain the sharp lower bound of the double Roman domination number of generalized Petersen graphs P (3 k , k) , and we construct solutions providing the upper bounds, which gives exact values of the double Roman domination number for all generalized Petersen graphs P (3 k , k) . This implies that P (3 k , k) is a double Roman graph if and only if either k ≡ 0 (mod 3) or k ∈ { 1 , 4 } . [ABSTRACT FROM AUTHOR]

For a simple graph G = (V , E) with no isolated vertices, a total Roman {3}-dominating function(TR3DF) on G is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that (i) ∑ w ∈ N (v) f (w) ≥ 3 if f (v) = 0 ; (ii) ∑ w ∈ N (v) f (w) ≥ 2 if f (v) = 1 ; and (iii) every vertex v with f (v) ≠ 0 has a neighbor u with f (u) ≠ 0 for every vertex v ∈ V (G) . The weight of a TR3DF f is the sum f (V) = ∑ v ∈ V (G) f (v) and the minimum weight of a total Roman {3}-dominating function on G is called the total Roman {3}-domination number denoted by γ t { R 3 } (G) . In this paper, we show that the total Roman {3}-domination problem is NP-complete for planar graphs and chordal bipartite graphs. Finally, we present a linear-time algorithm to compute the value of γ t { R 3 } for trees. [ABSTRACT FROM AUTHOR]

A dominating set in a graph G is a set of vertices S ⊆ V (G) such that any vertex of V − S is adjacent to at least one vertex of S. A dominating set S of G is said to be a perfect dominating set if each vertex in V − S is adjacent to exactly one vertex in S. The minimum cardinality of a perfect dominating set is the perfect domination number γ p (G). A function f : V (G) → { 0 , 1 , 2 } is a perfect Roman dominating function (PRDF) on G if every vertex u ∈ V for which f (u) = 0 is adjacent to exactly one vertex v for which f (v) = 2 . The weight of a PRDF is the sum of its function values over all vertices, and the minimum weight of a PRDF of G is the perfect Roman domination number γ R p (G). In this paper, we prove that for any nontrivial tree T, γ R p (T) ≥ γ p (T) + 1 and we characterize all trees attaining this bound. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) with vertex set V = V (G) and edge set E = E (G) , a Roman { 3 } -dominating function (R { 3 } -DF) is a function f : V (G) → { 0 , 1 , 2 , 3 } having the property that ∑ u ∈ N G (v) f (u) ≥ 3 , if f (v) = 0 , and ∑ u ∈ N G (v) f (u) ≥ 2 , if f (v) = 1 for any vertex v ∈ V (G) . The weight of a Roman { 3 } -dominating function f is the sum f (V) = ∑ v ∈ V (G) f (v) and the minimum weight of a Roman { 3 } -dominating function on G is the Roman { 3 } -domination number of G, denoted by γ { R 3 } (G) . Let G be a graph with no isolated vertices. The total Roman { 3 } -dominating function on G is an R { 3 } -DF f on G with the additional property that every vertex v ∈ V with f (v) ≠ 0 has a neighbor w with f (w) ≠ 0 . The minimum weight of a total Roman { 3 } -dominating function on G, is called the total Roman { 3 } -domination number denoted by γ t { R 3 } (G) . We initiate the study of total Roman { 3 } -domination and show its relationship to other domination parameters. We present an upper bound on the total Roman { 3 } -domination number of a connected graph G in terms of the order of G and characterize the graphs attaining this bound. Finally, we investigate the complexity of total Roman { 3 } -domination for bipartite graphs. [ABSTRACT FROM AUTHOR]