A note on the Roman domatic number of a digraph

Document Type : Original paper

Authors

RWTH Aachen University

Abstract

A  Roman dominating function on a digraph D with vertex set V(D) is a labeling f:V(D)→{0,1,2} such that every vertex with label 0 has an in-neighbor with label 2. A set {f1,f2,…,fd} of Roman dominating functions on D with the property that ∑i=1dfi(v)≤2 for each v∈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 dR(D). In this note, we study the Roman domatic number in digraphs, and we present some sharp bounds for dR(D). In addition, we determine the Roman domatic number of some digraphs. Some of our results are extensions of well-known properties of the Roman domatic number of undirected graphs.

Keywords

Main Subjects

References

[1] 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.
[2] E.J. Cockayne, P.A. Dreyer Jr, S.M. Hedetniemi, and S.T. Hedetniemi, Roman domination in graphs, Discrete Math. 278 (2004), no. 1-3, 11–22.
[3] O. Favaron, H. Karami, R. Khoeilar, and S.M. Sheikholeslami, On the Roman domination number of a graph, Discrete Math. 309 (2009), no. 10, 3447–3451.
4] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, Inc., New York, 1998.
[5] M.A. Henning, A characterization of Roman trees, Discuss. Math. Graph Theory 22 (2002), no. 2, 325–334.
[6] M.A. Henning, Defending the Roman Empire from multiple attacks, Discrete Math. 271 (2003), no. 1-3, 101–115.
[7] M. Kamaraj and P. Jakkammal, Directed Roman domination in digraphs, Int. J. Comb. Graph Theory Appl. 4 (2011), 103–116.
[8] C. Lee, On the domination number of a digraph, Michigan State University. Department of Mathematics, 1994.
[9] Mathieu Liedloff, Ton Kloks, Jiping Liu, and Sheng-Lung Peng, Efficient algorithms for roman domination on some classes of graphs, Discrete Appl. Math. 156 (2008), no. 18, 3400–3415.
[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] Z. Xie, G. Hao, and S. Wei, The Roman domination and domatic numbers of a digraph, Commun. Comb. Optim. 4 (2019), no. 1, 47–59.
Communications in Combinatorics and Optimization
Volume 5, Issue 1
June 2020
Pages 19-26

Files

Share

How to cite

Statistics