Search

A double Roman dominating function on a graph G=(V,E) is a function f:V→{0,1,2,3} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex u with f(u)=1 is adjacent to at least one vertex assigned 2 or 3. The weight of f equals w(f)=∑v∈Vf(v). The double Roman domination number γdR(G) of a graph G equals the minimum weight of a double Roman dominating function of G. We obtain closed expressions for the double Roman domination number of generalized Petersen graphs P(5k,k). It is proven that γdR(P(5k,k))=8k for k≡2,3mod5 and 8k≤γdR(P(5k,k))≤8k+2 for k≡0,1,4mod5. We also improve the upper bounds for generalized Petersen graphs P(20k,k).

The discharging method is most well-known for its central role in the proof of the Four Color Theorem. This proof technique was extensively applied to study various graph coloring problems, in particular on planar graphs. In this paper, we show that suitably altered discharging technique can also be used on domination-type problems. The general discharging approach for domination-type problems is illustrated on a specific domination-type problem, the double Roman domination on some generalized Petersen graphs. By applying this approach, we first prove that γdR(G)≥(3n/Δ(G) + 1) for any connected graph G with n≥2 vertices. As examples, we also determine the exact values of the double Roman domination numbers of the generalized Petersen graphs P(n, 1) and the double generalized Petersen graphs DP(n, 1). The obtained results imply that P(n, 1) is double Roman if and only if n ≠ 2 (mod 4) and DP(n, 1) is double Roman if and only if n ≡ 0 (mod 4).

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∈Vf(v). The double Roman domination number γdR(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 γdR(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(3k,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(3k,k). This implies that P(3k,k) is a double Roman graph if and only if either k≡0 (mod 3) or k∈{1,4}.

A double Roman dominating function on a graph G = (V , E) is a function f : V → { 0 , 1 , 2 , 3 } satisfying the condition that every vertex u for which f (u) = 0 is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and every vertex u with f (u) = 1 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 equals the minimum weight of a double Roman dominating function of G. We obtain closed expressions for the double Roman domination number of generalized Petersen graphs P (5 k , k) . It is proven that γ d R (P (5 k , k)) = 8 k for k ≡ 2 , 3 mod 5 and 8 k ≤ γ d R (P (5 k , k)) ≤ 8 k + 2 for k ≡ 0 , 1 , 4 mod 5 . We also improve the upper bounds for generalized Petersen graphs P (20 k , k) . [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]