Roman game domination subdivision number of a graph

Document Type: Research Paper

Authors

1 Azarbaijan Shahid Madani University

2 Azarbaijan University of Tarbiat Moallem

3 RWTH-Aachen University

Abstract

A Roman dominating function on a graph $G = (V,E)$ is a function $f : V\longrightarrow \{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 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

Main Subjects


M. Atapour, A. Khodkar and S. M. Sheikholeslami (2010). Trees whose Roman domination subdivision number is 2. Util. Math.. 82, 227-240
E. W. Chambers, B. Kinnersley, N. Prince and D. B. West (2009). Extremal problems for Roman domination. SIAM J. Discrete Math.. 23, 1575-1586
E. J. Cockayne, P. A. Dreyer Jr., S. M. Hedetniemi and S. T. Hedetniemi (2004). Roman domination in graphs. Discrete Math.. 278, 11-22
E. J. Cockayne, P. J. P. Grobler, W. R. Gr"{u}ndlingh, J. Munganga and J. H. van Vuuren (2005). Protection of a graph. Util. Math.. 67, 19-32
O. Favaron, H. Karami and S. M. Sheikholeslami Game domination subdivision number of a graph. J. Comb. Optim., (to appear).
O. Favaron, H. Karami and S. M. Sheikholeslami (2009). On the Roman domination number in graphs. Discrete Math.. 309, 3447-3451
T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in graphs. Marcel Dekker, Inc., New York.
M. A. Henning (2002). A characterization of Roman trees. Discuss. Math. Graph Theory. 22, 325-334
N. Jafari Rad and L. Volkmann (2011). Roman domination perfect graphs. An. Stiint. Univ. Ovidius Constanta Ser. Mat.. 19, 167-174
C. S. ReVelle and K. E. Rosing (2000). Defendens imperium romanum: a classical problem in military strategy. Amer. Math. Monthly. 107, 585-594
I. Stewart (1999). Defend the roman empire. Sci. Amer.. 281 (6), 136-139
L. Volkmann (2008). A characterization of bipartite graphs with independence number half their order. Australas. J. Combin.. 41, 219-222
D. B. West (2000). Introduction to Graph Theory. Prentice-Hall, Inc..