On the roman domination number of generalized Sierpiński graphs
2017; University of Niš; Volume: 31; Issue: 20 Linguagem: Inglês
10.2298/fil1720515r
ISSN2406-0933
AutoresFatemeh Ramezani, Erick D. Rodríguez-Bazán, Juan A. Rodríguez‐Velázquez,
Tópico(s)Limits and Structures in Graph Theory
ResumoA 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.
Referência(s)