Signed $k$-domatic numbers of graphs

Abstract

Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V(G)$. A function $f:V(G)\to \{\pm 1,\pm 2,\dots ,\pm k\}$ is called a signed $\{k\}$-dominating function if

$$\sum _{u\in N[v]}f(u)\ge k$$

for each vertex $v\in V(G)$.

The signed $\{1\}$-dominating function is the same as the ordinary signed domination. A set $\{f_1,f_2,\dots ,f_d\}$ of signed $\{k\}$-dominating functions on $G$ with the property that

$$\sum _{i=1}^d{f}_i(v)\le k$$

for each $v\in V(G)$, is called a $signed\{k\}-dominatingfamily$ (of functions) on $G$. The maximum number of functions in a signed $\{k\}$-dominating family on $G$ is the $signed\{k\}-domaticnumber$ of $G$, denoted by $d_{\{k\}S}(G)$. Note that $d_{\{1\}S}(G)$ is the classical signed domatic number $d_s(G)$.

In this paper, we initiate the study of signed $\{k\}$-domatic numbers in graphs, and we present some sharp upper bounds for $d_{\{k\}S}(G)$. In addition, we determine $d_{\{k\}S}(G)$ for several classes of graphs. Some of our results are extensions of known properties of the signed domatic number.