Double Roman Graphs in P(3k, k)

Abstract

A double Roman dominating function on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2,3\}$ with the properties that if $f\left(u\right)=0$, then vertex u is adjacent to at least one vertex assigned 3 or at least two vertices assigned 2, and if $f\left(u\right)=1$, then vertex u is adjacent to at least one vertex assigned 2 or 3. The weight of f equals $w\left(f\right)={\sum }_{v\in V}f\left(v\right)$. The double Roman domination number ${\gamma }_{dR}\left(G\right)$ 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 ${\gamma }_{dR}\left(G\right)=3\gamma \left(G\right)$, where $\gamma \left(G\right)$ 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\equiv 0$ (mod 3) or $k\in \{1,4\}$.