On the roman domination number of generalized Sierpiński graphs


F Ramezani, E D Rodríguez-Bazan, J A Rodríguez-Velázquez




A map f : V → {0, 1, 2} is a Roman dominating function on a graph G = (V,E) if for every vertex v ∈ V with f (v) = 0, there exists a vertex u, adjacent to v, such that f (u) = 2. The weight of a Roman dominating function is given by f (V) = ∑ u∈V f (u). The minimum weight among all Roman dominating functions on G is called the Roman domination number of G. In this article we study the Roman domination number of Generalized Sierpiński graphs S(G, t). More precisely, we obtain a general upper bound on the Roman domination number of S(G, t) and discuss the tightness of this bound. In particular, we focus on the cases in which the base graph G is a path, a cycle, a complete graph or a graph having exactly one universal vertex.