Roman game domination subdivision number of a graph

A Roman dominating function on a graph G = (V,E) is a function f : V\longrightarrow \{۰, ۱, ۲\} satisfying the condition that every vertex v for which f (v) = ۰ is adjacent to at least one vertex u for which f (u) = ۲. The weight of a Roman dominating function is the value w(f)=\sum_{v\in V}f(v). The Roman domination number of a graph G, denoted by \gamma_R(G), equals the minimum weight of a Roman dominating function on G. The Roman game domination subdivision number of a graph G is defined by the following game. Two players \mathcal D and \mathcal A, \mathcal D playing first, alternately mark or subdivide an edge of G which is not yet marked nor subdivided. The game ends when all the edges of G are marked or subdivided and results in a new graph G'. The purpose of \mathcal D is to minimize the Roman domination number \gamma_R(G') of G' while \mathcal A tries to maximize it. If both \mathcal A and \mathcal D play according to their optimal strategies, \gamma_R(G') is well defined. We call this number the {\em Roman game domination subdivision number} of G and denote it by \gamma_{Rgs}(G). In this paper we initiate the study of the Roman game domination subdivision number of a graph and present sharp bounds on the Roman game domination subdivision number of a tree.

Keywords:

Roman domination number , Roman game domination subdivision number , tree