On the Roman domination number of generalized Sierpinski graphs

Abstract

A map $f:V\to \{0,1,2\}$ is a Roman dominating function on a graph $G=(V,E)$ if for every vertex $v\in 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)={\sum }_{u\in V}f(u)$. The minimum weight of a Roman dominating function 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 we 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.