Regular graphs with large Italian domatic number

Document Type : Original paper

Author

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

Abstract

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.

Keywords

Main Subjects

References

[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 http://web.olivet.edu/~sjlyle/ItalianDomatic.html.
[7] B. McKay, Description of graph6, sparse6 and digraph6 encodings, 2015, http://users.cecs.anu.edu.au/~bdm/data/formats.txt.
[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, http://www.sagemath.org.
[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.
Communications in Combinatorics and Optimization
Volume 7, Issue 2
December 2022
Pages 257-271

Files

Share

How to cite

Statistics