Roman game domination subdivision number of a graph
| Autor: | Jafar Amjadi, Hossein Karami, Seyed Mahmoud Sheikholeslami, Lutz Volkmann |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: | |
| Zdroj: | Transactions on Combinatorics, Vol 2, Iss 4, Pp 1-12 (2013) |
| Druh dokumentu: | article |
| ISSN: | 2251-8657 2251-8665 |
| Popis: | A {em Roman dominating function} on a graph $G = (V ,E)$ is a function $f : Vlongrightarrow {0, 1, 2}$ satisfying the condition that every vertex $v$ for which $f (v) = 0$ is adjacent to at least one vertex $u$ for which $f (u) = 2$. The {em weight} of a Roman dominating function is the value $w(f)=sum_{vin 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 dominating 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|