The Italian domatic number of a digraph

Document Type : Original paper

Author

RWTH Aachen University

Abstract

An Italian dominating function on a digraph $D$ with vertex set $V(D)$ is defined as a function $f\colon V(D)\to \{0, 1, 2\}$ such that every vertex $v\in V(D)$ with $f(v)=0$ has at least two in-neighbors assigned 1 under $f$ or one in-neighbor $w$ with $f(w)=2$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct Italian 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 an  Italian dominating family (of functions) on $D$. The maximum number of functions in an Italian dominating family on $D$ is the  Italian domatic number of $D$, denoted by $d_{I}(D)$. In this paper we initiate the study of the Italian domatic number in digraphs, and we present some sharp bounds for $d_{I}(D)$. In addition, we determine the Italian domatic number of some digraphs.

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] M. Chellali, T.W. Haynes, S.T. Hedetniemi, and A.A. McRae, Roman $\{2\}$-domination, Discrete Appl. Math. 204 (2016), 22–28.
[3] 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.
[4] 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.
[5] G. Hao and S. Xie, Z. Wei, The Roman domination and domatic numbers of a digraph, Commun. Comb. Optim. 4 (2019), no. 1. 47-59.
[6] G. Hao, Z. Xie, and X. Chen, A note on Roman domination of digraphs, Discuss. Math. Graph Theory 39 (2019), no. 1, 13–21.
[7] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Fundamentals of domination in graphs, Marcel Dekker, Inc., New York, 1998.
[8] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), 557–564.
[9] M. Kamaraj and V. Hemalatha, Directed Roman domination in digraphs, Int. J. Comb. Graph Theory Appl. 4 (2011), 103–116.
[10] C.-H. Liu and G.J. Chang, Upper bounds on Roman domination numbers of graphs, Discrete Math. 312 (2012), no. 7, 1386–1391.
[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] L. Volkmann, Italian domination in digraphs, J. Combin. Math. Combin. Comput. (to appear).
Communications in Combinatorics and Optimization
Volume 4, Issue 1
June 2019
Pages 61-70

Files

Share

How to cite

Statistics