Regular graphs with large Italian domatic number

Document Type : Original paper


Department of Mathematics and Computer Science, Olivet Nazarene University, Bourbonnais, IL


For a graph $G$, an Italian dominating function is a function $f: V(G) \rightarrow \{0,1,2\}$ such that for each vertex $v \in V(G)$ either $f(v) \neq 0$, or $\sum_{u \in N(v)} f(u) \geq 2$. If a family $\mathcal{F} = \{f_1, f_2, \dots, f_t\}$ of distinct Italian dominating functions satisfy $\sum^t_{i = 1} f_i(v) \leq 2$ for each vertex $v$, then this is called an Italian dominating family. In [L. Volkmann, The {R}oman {$\{2\}$}-domatic number of graphs, Discrete Appl. Math.  258 (2019), 235--241], Volkmann defined the Italian domatic number of $G$, $d_{I}(G)$, as the maximum cardinality of any Italian dominating family. In this same paper, questions were raised about the Italian domatic number of regular graphs. In this paper, we show that two of the conjectures are false, and examine some exceptions to a Nordhaus-Gaddum type inequality.


Main Subjects

[1] G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H. M´elot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (2013), no. 1-2, 311–314.
[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] M.A. Henning and S.T Hedetniemi, Defending the Roman Empire–A new strategy, Discrete Math. 266 (2003), no. 1-3, 239–251.
[5] M.A. Henning and W.F. Klostermeyer, Italian domination in trees, Discrete Appl. Math. 217 (2017), no. part 3, 557–564.
[6] J. Lyle, Regular graphs with large Italian domatic number: Sage code, 2021, located at
[7] B. McKay, Description of graph6, sparse6 and digraph6 encodings, 2015,
[8] J. Petersen, Die Theorie der regul¨aren graphs, Acta Math. 15 (1891), no. 1, 193–220.
[9] W. A. Stein and et al., Sage Mathematics Software (Version 8.6.4), The Sage Development Team, 2021,
[10] I. Stewart, Defend the Roman Empire!, Scientific American (1999), 136–138.
[11] L. Volkmann, The Italian domatic number of a digraph, Commun. Comb. Optim. 4 (2019), no. 1, 61–70.
[12] L. Volkmann, The Roman {2}-domatic number of graphs, Discrete Appl. Math. 258 (2019), 235–241.