The signed (k,k) -domatic number of digraphs
Seyed Mahmoud Sheikholeslami, Lutz Volkmann · University of Zagreb University Computing Centre (SRCE) · 2012
Let D be a finite and simple digraph with vertex set V (D), and let f : V (D) → {-1, 1} be a two-valued function.If k ≥ 1 is an integer and x∈N -[v] f (x) ≥ k for each v ∈ 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 , . . ., f d } of distinct signed k-dominating functions on D with the property that d i=1 f i (x) ≤ k for each x ∈ V (D), is called a signed (k, k)-dominating family (of functions) on D. The maximum number of functions in a signed (k, k)-dominating family on D is the signed (k, k)-domatic number on D, denoted by d k S (D).In this paper, we initiate the study of the signed (k, k)-domatic number of digraphs, and we present different bounds on d k S (D).Some of our results are extensions of well-known properties of the signed domatic number d S (D) = d 1 S (D) of digraphs D as well as the signed (k, k)-domatic number d k S (G) of graphs G.