Graphs with small Italian domatic number

An Italian dominating function of a graph G is a function f:V(G)→{0,1,2} such that for each vertex v∈V(G) either f(v)≠0, or ∑u∈N(v)f(u)≥2. If a family F={f1,f2,…,ft} of Italian dominating functions satisfy ∑i=1tfi(v)≤2 for each vertex v, then this is called an Italian dominating family. The Italian domatic number of a graph G, denoted dI(G), is the maximum cardinality of any such family of distinct Italian dominating functions. This paper considers graphs with small Italian domatic number. In particular, it is shown that a graph must have leaves if it has an Italian domatic number of two, but that determining whether or not a graph has Italian domatic number of three is NP-complete. In addition, trees with an Italian domatic number of three are classified, completely determining the Italian domatic number of trees.