Geodesic
A Note on Roman Domination of Digraphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 13-21.

Voir la notice de l'article provenant de la source Library of Science

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S is adjacent from at least one vertex in S. The domination number of a digraph D, denoted by γ(D), is the minimum cardinality of a dominating set of D. 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 ω (f) = Σ_ v ∈ V(D) f(v). The Roman domination number of a digraph D, denoted by γ_R (D), is the minimum weight of an RDF on D. In this paper, for any integer k with 2 ≤ k ≤γ(D), we characterize the digraphs D of order n ≥ 4 with δ − (D) ≥ 1 for which γ_R(D) = (D) + k holds. We also characterize the digraphs D of order n ≥ k with γ_R(D) = k for any positive integer k. In addition, we present a Nordhaus-Gaddum bound on the Roman domination number of digraphs.
Keywords: Roman domination number, domination number, digraph, Nordhaus-Gaddum 
@article{DMGT_2019_39_1_a1,
     author = {Chen, Xiaodan and Hao, Guoliang and Xie, Zhihong},
     title = {A {Note} on {Roman} {Domination} of {Digraphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {13--21},
     publisher = {mathdoc},
     volume = {39},
     number = {1},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a1/}
}
TY  - JOUR
AU  - Chen, Xiaodan
AU  - Hao, Guoliang
AU  - Xie, Zhihong
TI  - A Note on Roman Domination of Digraphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 13
EP  - 21
VL  - 39
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a1/
LA  - en
ID  - DMGT_2019_39_1_a1
ER  - 
%0 Journal Article
%A Chen, Xiaodan
%A Hao, Guoliang
%A Xie, Zhihong
%T A Note on Roman Domination of Digraphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 13-21
%V 39
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a1/
%G en
%F DMGT_2019_39_1_a1
Chen, Xiaodan; Hao, Guoliang; Xie, Zhihong. A Note on Roman Domination of Digraphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 1, pp. 13-21. http://geodesic.mathdoc.fr/item/DMGT_2019_39_1_a1/

[1] J.D. Alvarado, S. Dantas and D. Rautenbach, Strong equality of Roman and weak Roman domination in trees, Discrete Appl. Math. 208 (2016) 19-26. doi: 10.1016/j.dam.2016.03.004

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (GTM 244, Springer, 2008).

[3] Y. Caro and M.A. Henning, Directed domination in oriented graphs, Discrete Appl. Math. 160 (2012) 1053-1063. doi: 10.1016/j.dam.2011.12.027

[4] E.W. Chambers, B. Kinnersley, N. Prince and D.B. West, Extremal problems for Roman domination, SIAM J. Discrete Math. 23 (2009) 1575-1586. doi: 10.1137/070699688

[5] M. Chellali and N.J. Rad, Strong equality between the Roman domination and in- dependent Roman domination numbers in trees, Discuss. Math. Graph Theory 33 (2013) 337-346. doi: 10.7151/dmgt.1669

[6] Y. Fu, Dominating set and converse dominating set of a directed graph, Amer. Math. Monthly 75 (1968) 861-863. doi: 10.2307/2314337

[7] X. Fu, Y. Yang and B. Jiang, Roman domination in regular graphs, Discrete Math. 309 (2009) 1528-1537. doi: 10.1016/j.disc.2008.03.006

[8] Š. Gyürki, On the difference of the domination number of a digraph and of its reverse, Discrete Appl. Math. 160 (2012) 1270-1276. doi: 10.1016/j.dam.2011.12.029

[9] G. Hao and J. Qian, On the sum of out-domination number and in-domination number of digraphs, Ars Combin. 119 (2015) 331-337.

[10] T.W. Haynes, S.T. Hedetniemi and P.J. Slater, Domination in Graphs: Advanced Topics (Marcel Dekker, Inc., New York, 1998).

[11] M. Kamaraj and P. Jakkammal, Directed Roman domination in digraphs, submitted.

[12] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012) 1386-1391. doi: 10.1016/j.disc.2011.12.021

[13] C.-H. Liu and G.J. Chang, Roman domination on strongly chordal graphs, J. Comb. Optim. 26 (2013) 608-619. doi: 10.1007/s10878-012-9482-y

[14] S.M. Sheikholeslami and L. Volkmann, The Roman domination number of a digraph, Acta Univ. Apulensis Math. Inform. 27 (2011) 77-86.

[15] S.M. Sheikholeslami and L. Volkmann, Signed Roman domination in digraphs, J. Comb. Optim. 30 (2015) 456-467. doi: 10.1007/s10878-013-9648-2

[16] T.K. Šumenjak, P. Pavlič and A. Tepeh, On the Roman domination in the lexico- graphic product of graphs, Discrete Appl. Math. 160 (2012) 2030-2036. doi: 10.1016/j.dam.2012.04.008

[17] L. Volkmann, Signed total Roman domination in digraphs, Discuss. Math. Graph Theory 37 (2017) 261-272. doi: 10.7151/dmgt.1929

[18] H.-M. Xing, X. Chen and X.-G. Chen, A note on Roman domination in graphs, Discrete Math. 306 (2006) 3338-3340. doi: 10.1016/j.disc.2006.06.018.