On signed cycle domination in graphs

Let G = (V, E) be a graph, a function f : E -> {- 1, 1} is said to be an signed cycle dominating function (SCDF) of G if Sigma(e is an element of E(C)) f(e) >= 1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as gamma'sc(G) = min{Sigma(e is an element of E(G)) f(e) vertical bar f is an SCDF of G}. In this paper, we obtain bounds on gamma'sc(G), characterize all connected graphs G with gamma'sc(G) = vertical bar E(G)vertical bar - 2, and determine the exact value of gamma'(sc)(G) for some special classes of graphs G. In addition, we pose some open problems and conjectures. (C) 2008 Elsevier B.V. All rights reserved.