آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 118 |
| تعداد مقالات | 1,454 |
| تعداد مشاهده مقاله | 1,568,965 |
| تعداد دریافت فایل اصل مقاله | 1,469,573 |
The Roman domination and domatic numbers of a digraph | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 5، دوره 4، شماره 1، شهریور 2019، صفحه 47-59 اصل مقاله (382.24 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2019.26356.1101 | ||
| نویسندگان | ||
| Zhihong Xie1؛ Guoliang Hao* 1؛ Shouliu Wei2 | ||
| 1College of Science, East China University of Technology, Nanchang, P. R. China | ||
| 2Department of Mathematics, Minjiang University, Fuzhou, China | ||
| چکیده | ||
| A Roman dominating function (RDF) on a digraph $D$ is a function $f: V(D)\rightarrow {0,1,2}$ satisfying the condition that every vertex $v$ with $f(v)=0$ has an in-neighbor $u$ with $f(u)=2$. The weight of an RDF $f$ is the value $\sum_{v\in V(D)}f(v)$. The Roman domination number of a digraph $D$ is the minimum weight of an RDF on $D$. A set $\{f_1,f_2,\dots,f_d\}$ of Roman dominating functions on $D$ with the property that $\sum_{i=1}^df_i(v)\le2$ for each $vin V(D)$, is called a Roman dominating family (of functions) on $D$. The maximum number of functions in a Roman dominating family on $D$ is the Roman domatic number of $D$, denoted by $d_{R}(D)$. In this paper we continue the investigation of the Roman domination number, and we initiate the study of the Roman domatic number in digraphs. We present some bounds for $d_{R}(D)$. In addition, we determine the Roman domatic number of some digraphs. | ||
| کلیدواژهها | ||
| Roman dominating function؛ Roman domination number؛ Roman domatic number؛ digraph | ||
| مراجع | ||
|
[1] H. Abdollahzadeh Ahangar, M.A. Henning, C. L¨owenstein, Y. Zhao, and V. Samodivkin, Signed Roman domination in graphs, J. Comb. Optim. 27 (2014), no. 2, 241–255.
[2] J.D. Alvarado, S. Dantas, and D. Rautenbach, Relating 2-rainbow domination to Roman domination, Discuss. Math. Graph Theory 37 (2017), no. 4, 953–961.
[3] E.W. Chambers, B. Kinnersley, N. Prince, and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009), no. 3, 1575–1586.
[4] G. Hao, X. Chen, and L. Volkmann, Double Roman domination in digraphs, Bull. Malays. Math. Sci. Soc. (2017), doi:10.1007/s40840–017–0582–9.
[5] G. Hao, Z. Xie, and X. Chen, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019), no. 1, 13–21.
[6] M. Kamaraj and P. Jakkammal, Directed Roman domination in digraphs, Int. J. Comb. Graph Theory Appl. 4 (2011), 103–116.
[7] A.P. Kazemi, S.M. Sheikholeslami, and L. Volkmann, The Roman $(k, k)$-domatic number of a graph, Ann. Math. Inform. 38 (2011), 45–57.
[8] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012), no. 7, 1386–1391.
[9] , Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013), no. 3, 608–619.
[10] C.S. ReVelle and K.E. Rosing, Defendens imperium Romanum: a classical problem in military strategy, Amer. Math. Monthly 107 (2000), no. 7, 585–594.
[11] S.M. Sheikholeslami and L. Volkmann, The Roman domatic number of a graph, Appl. Math. Lett. 23 (2010), no. 10, 1295–1300.
[12] S.M. Sheikholeslami and L. Volkmann, The Roman domination number of a digraph, Acta Univ. Apulensis Math. Inform. 27 (2011), 77–86.
[13] I. Stewart, Defend the roman empire!, Sci. Amer. 281 (1999), no. 6, 136–138.
[14] H. Tan, H. Liang, R. Wang, and J. Zhou, Computing Roman domatic number of graphs, Inform. Process. Lett. 116 (2016), no. 9, 554–559.
[15] F. Xueliang, Y. Yuansheng, and J. Baoqi, Roman domination in regular graphs, Discrete Math. 309 (2009), no. 6, 1528–1537.
[16] B. Zelinka, Signed domination numbers of directed graphs, Czech. Math. J. 55 (2005), no. 2, 479–482.
[17] E. Zhu and Z. Shao, Extremal problems on weak Roman domination number, Inform. Process. Lett. 138 (2018), 12–18. | ||
|
آمار تعداد مشاهده مقاله: 941 تعداد دریافت فایل اصل مقاله: 742 |
||