top library bulletin
bar home editorial guideline content
dot
 
Volume 36 • Number 1 • 2013
 
• Signed $k$-Domatic Numbers of Digraphs
H. Aram, M. Atapour, S. M. Sheikholeslami and L. Volkmann

Abstract.
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.

2010 Mathematics Subject Classification: 05C20, 05C69, 05C45


Full text: PDF
 
dot