The Roman domination and domatic numbers of a digraph

Document Type : Original paper

Authors

1 College of Science, East China University of Technology, Nanchang, P. R. China

2 Department of Mathematics, Minjiang University, Fuzhou, China

Abstract

A Roman dominating function (RDF) on a digraph D is a function f:V(D)→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 ∑v∈V(D)f(v). The Roman domination number of a digraph D is the minimum weight of an RDF on D. A set {f1,f2,…,fd} of Roman dominating functions on D with the property that ∑i=1dfi(v)≤2 for each vinV(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 dR(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 dR(D). In addition, we determine the Roman domatic number of some digraphs.

Keywords

Main Subjects

References

[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.
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 47-59

Files

Share

How to cite

Statistics