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\colon V(D)\to \{0, 1, 2\}$ such that every vertex with label $0$ has an in-neighbor with label $2$. A set $\{f_1,f_2,\ldots,f_d\}$ of Roman dominating functions on $D$ with the property that $\sum_{i=1}^d f_i(v)\le 2$ for each $v\in 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 note, we study the Roman domatic number in digraphs, and we present some sharp bounds for $d_{R}(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