The Complexity of Computing Signed (Total) Domatic Numbers of Graphs

Abstract

Let \( G = (V, E) \) be a graph. A function \( f: V \to \{-1, 1\} \) is called a signed dominating function on \( G \) if \( \sum_{u \in N_G[v]} f(u) \geq 1 \) for each \( v \in V \), where \( N_G[v] \) is the closed neighborhood of \( v \). A set \( \{f_1, f_2, \ldots, f_d\} \) of signed dominating functions on \( G \) is called a signed dominating family (of functions) on \( G \) if \( \sum_{i=1}^d f_i(v) \leq 1 \) for each \( v \in V \). The signed domatic number of \( G \) is the maximum number of functions in a signed dominating family on \( G \). The signed total domatic number is defined similarly, by replacing the closed neighborhood \( N_G[v] \) with the open neighborhood \( N_G(v) \) in the definition. In this paper, we prove that the problems of computing the signed domatic number and the signed total domatic number of a given graph are both NP-hard, even if the graph has bounded maximum degree. To the best of our knowledge, these are the first NP-hardness results for these two variants of the domatic number.