پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شماره‌ها | 1,706 |
| تعداد مقالات | 13,973 |
| تعداد مشاهده مقاله | 33,601,008 |
| تعداد دریافت فایل اصل مقاله | 13,324,523 |
Roman game domination subdivision number of a graph | ||
| Transactions on Combinatorics | ||
| مقاله 1، دوره 2، شماره 4، اسفند 2013، صفحه 1-12 اصل مقاله (358.09 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2013.3341 | ||
| نویسندگان | ||
| Jafar Amjadi1؛ Hossein Karami1؛ Seyed Mahmoud Sheikholeslami* 2؛ Lutz Volkmann3 | ||
| 1Azarbaijan Shahid Madani University | ||
| 2Azarbaijan University of Tarbiat Moallem | ||
| 3RWTH-Aachen University | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| Roman domination number؛ Roman game domination subdivision number؛ tree | ||
| مراجع | ||
|
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.
| ||
|
آمار تعداد مشاهده مقاله: 5,148 تعداد دریافت فایل اصل مقاله: 3,595 |
||