A note on Roman domination in graphs - Rad, Nader Jafari, (Utilitas Mathematica, 2010)
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 Mk+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.