On the Roman domination number of generalized Sierpiński graphs

Identifier:  imarina:5132236

Handle: https://hdl.handle.net/20.500.11797/imarina5132236

Authors:  Ramezani, F; Rodríguez-Bazan, ED; Rodríguez-Velázquez, JA

Abstract:
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.