p. 9 - 14 Upper signed
k-domination number
H. Aram, S. M. Sheikholeslami, L. Volkmann Received: January 14, 2011;
Accepted: November 24, 2011
Abstract.
Let k ³ 1 be an integer and let
D = (V, A) be a finite simple digraph in which d(_{D}^{-}v) ³ 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. An
SkDF f of a digraph D is minimal if there is no SkDF
g ¹ f
such that
g(v) £ f(v)
for each
v Î V.
The maximum values of
å_{v Î V} f(v),
taken over all minimal signed k-dominating
functions f, is called the upper signed k-domination
number
G_{kS}(D). In this paper, we present a sharp upper
bound for
G_{kS}(D).
Keywords:
Signed k-dominating function; mimimal signed k-dominating function;
upper signed k-domination number; directed graph.
AMS Subject classification:
Primary: 05C20, 05C69, 05C45
PDF Compressed Postscript Version to read ISSN 0862-9544 (Printed edition) Faculty of Mathematics, Physics and Informatics Comenius University 842 48 Bratislava, Slovak Republic Telephone: + 421-2-60295111 Fax: + 421-2-65425882 e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc © 2012, ACTA MATHEMATICA UNIVERSITATIS COMENIANAE |