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)\ge 1$ for each $v\in V$, where $N_G[v]$ is the closed neighborhood of $v$. A set $\{f_1,f_2,\dots ,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)\le 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.