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 \{-1,1\}$ is called a signed $k$-dominating function if $\sum _{u\in N(v)}f(u)\ge k$ for each vertex $v\in V(G)$. 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 1$ for each $v\in V(G)$, is called a signed $k$-dominating family (of functions) on $G$. The maximum number of functions in a signed $k$-dominating family on $G$ is the signed $k$-domatic number of $G$, denoted by $d_{kS}(G)$. In this paper, we initiate the study of signed $k$-domatic numbers in graphs and we present some sharp upper bounds for $d_{kS}(G)$. In addition, we determine the signed $k$-domatic number of complete graphs.