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:V(D){0,1,2} such that every vertex vV(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 {f1,f2,,fd} of distinct Italian dominating functions on D with the property that i=1dfi(v)2 for each vV(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 dI(D). In this paper we initiate the study of the Italian domatic number in digraphs, and we present some sharp bounds for dI(D). In addition, we determine the Italian domatic number of some digraphs.

Keywords

Main Subjects


[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).