×

Signed domination and signed domatic numbers of digraphs. (English) Zbl 1227.05207

Summary: Let \(D\) be a finite and simple digraph with the vertex set \(V(D)\), and let \(f: V(D)\to \{-1,1\}\) be a two-valued function. If \(\sum_{x\in N^-[v]} f(x)\geq 1\) 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 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 \(\gamma_S(D)\) of \(D\). A set \(\{f_1,f_2,\dots, f_d\}\) of signed dominating functions on \(D\) with the property that \(\sum_{i=1} f_i(x)\leq 1\) for each \(x\in 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 \(ds(D)\).
In this work we show that \(4- n\leq\gamma_S(D)\leq n\) for each digraph \(D\) of order \(n\geq 2\), and we characterize the digraphs attending the lower bound as well as the upper bound. Furthermore, we prove that \(\gamma_S(D)+ ds(D)\leq n+ 1\) for any digraph \(D\) of order \(n\), and we characterize the digraphs \(D\) with \(\gamma_S(D)+ d_S(D)= n+ 1\). Some of our theorems imply well-known results on the signed domination number of graphs.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20 Directed graphs (digraphs), tournaments
05C22 Signed and weighted graphs
PDFBibTeX XMLCite
Full Text: DOI Link