Roman domination in regular graphs

AbstractA Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{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 a Roman dominating function is the value f(V(G))=∑u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11–22] showed that γ(G)≤γR(G)≤2γ(G) and defined a graph G to be Roman if γR(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P3k,P3k+2,C3k,C3k+2 for k≥1, Km,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs C(n;{1,3})(n≥7,n⁄≡4(mod5)) and C(n;{1,2,…,k})(k≤⌊n2⌋), n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)(n≠4k+2,n≡0 (mod 4) and 0≤k≤⌊n2⌋), P(n,1) (n⁄≡2 (mod 4)), P(n,3) (n≥7,n⁄≡3 (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs C5m□C5n(m≥1,n≥1) are Roman graphs