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 dD-(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 GkS(D). In this paper, we present a sharp upper bound for GkS(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 |