On the Roman domination number of generalized Sierpinski graphs

Fatemeh Ramezani, Erick D. Rodriguez-Bazan, Juan A. Rodriguez-Velazquez

Published 2016-05-23Version 1

A map $f : V \rightarrow \{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\'{n}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.