Signed $k$-Domatic Numbers of Digraphs

H. Aram ; M. Atapour ; S. M. Sheikholeslami ; L. Volkmann

Bulletin of the Malaysian Mathematical Society, Tome 36 (2013) no. 1

Résumé

Let $D$ be a finite and simple digraph with vertex set $V(D)$, and let $f:V(D)\rightarrow\{-1,1\}$ be a two-valued function. If $k\ge 1$ is an integer and $\sum_{x\in N^-[v]}f(x)\ge k$ for each $v\in V(D)$, where $N^-[v]$ consists of $v$ and all vertices of $D$ from which arcs go into $v$, then $f$ is a signed $k$-dominating function on $D$. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct signed $k$-dominating functions of $D$ with the property that $\sum_{i=1}^df_i(v)\le 1$ for each $v\in V(D)$, is called a {\em signed $k$-dominating family} (of functions) of $D$. The maximum number of functions in a signed $k$-dominating family of $D$ is the {\em signed $k$-domatic number} of $D$, denoted by $d_{kS}(D)$. In this note we initiate the study of the signed $k$-domatic numbers of digraphs and present some sharp upper bounds for this parameter.

Détail

Classification : 05C20, 05C69, 05C45