Signed domination and signed domatic numbers of digraphs

Volkmann, Lutz

Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 3, pp. 415-427

Résumé

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₁,f₂,...,f_d of signed dominating functions on D with the property that ∑_i = 1^d 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.

Détail

Keywords: digraph, oriented graph, signed dominating function, signed domination number, signed domatic number