Signed domination and signed domatic numbers of digraphs
Lutz Volkmann · Discussiones Mathematicae Graph Theory · 2011
Let D be a finite and simple digraph with the vertex set V (D), and let f : V (D) → {-1, 1} be a two-valued function.If x∈N -[v] f (x) ≥ 1 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 dominating function on D. The sum f (V (D)) is called the weight w(f ) of f .The minimum of weights w(f ), taken over all signed dominating functions f on D, is the signed domination number γ S (D) of D. A set {f 1 , f 2 , . . ., f d } of signed dominating functions on D with the property that d i=1 f i (x) ≤ 1 for each x ∈ V (D), is called a signed dominating family (of functions) on D. The maximum number of functions in a signed dominating family on D is the signed domatic number of D, denoted by d S (D).In this work we show that 4 -n ≤ γ S (D) ≤ n for each digraph D of order n ≥ 2, and we characterize the digraphs attending the lower bound as well as the upper bound.Furthermore, we prove that γ S (D)+ d S (D) ≤ n + 1 for any digraph D of order n, and we characterize the digraphs D with γ S (D) + d S (D) = n + 1.Some of our theorems imply well-known results on the signed domination number of graphs.