A note on Roman domination in graphs

Abstract

A Roman dominating function on a graph G= (V, E) is a function f : V(G) → {0,1,2} satisfying the condition that every vertex u for which f(it) = 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 f(u). The Roman domination number, _γR(G), of G is the minimum weight of a Roman dominating function on G. A graph G is Roman if _γR(G) = 2_γ(G). Cockayne et al. in [1] found some Roman graphs and left finding other classes of Roman graphs as an open problem. Let M(G) be the graph obtained from G by applying Mycielski's construction. The κ-th Mycielski graph of G is defined recursively by M°(G) = G and M^k+1(G) = M(M^κ(G)) for κ ≥ 1. In this paper, we investigate the relationship between _γR(G) and _γR(M(G)) for any graph G, and prove that: (1) any graph G with _γR(M(G)) = 1+_γR(G) is a Roman graph, and (2) if G is a Roman graph and _γ(G) ≠ _γt(G), where _γt(G) is the total domination number of G, then for any positive integer κ, M^κ(G) is a Roman graph.