The signed k-domination number of directed graphs
Maryam Atapour, Seyed Mahmoud Sheikholeslami, Rana Hajypory, Lutz Volkmann · Open Mathematics · 2010
Abstract Let k ≥ 1 be an integer, and let D = (V; A) be a finite simple digraph, for which d D− ≥ k − 1 for all v ɛ V. A function f: V → {−1; 1} is called a signed k-dominating function (SkDF) if f(N −[v]) ≥ k for each vertex v ɛ V. The weight w(f) of f is defined by $$ \sum olimits_{v \in V} {f(v)} $$. The signed k-domination number for a digraph D is γkS(D) = min {w(f|f) is an SkDF of D. In this paper, we initiate the study of signed k-domination in digraphs. In particular, we present some sharp lower bounds for γkS(D) in terms of the order, the maximum and minimum outdegree and indegree, and the chromatic number. Some of our results are extensions of well-known lower bounds of the classical signed domination numbers of graphs and digraphs.