Double Roman Graphs in P (3 k , k )

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 } .