Vol. LXXXI, 1 (2012)
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

Acta Mathematica Universitatis Comenianae
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:    Internet: