For a graph  without isolated vertex, a function  is said to be a signed star dominating function of G if  for every  where  The minimum value of  taken over all signed star dominating functions f of G, is called the signed star domination number of G. In this paper, we provide a new upper bound for the signed star domination number of a general graph, in terms of the matching number of the graph, compute the exact values of signed star domination number of some regular graphs, and construct a graph H from any given graph G such that the edge covering number of H is equal to the signed star domination number of G. Finally, we present a linear time algorithm to compute the signed star domination number of cacti, a super class of trees. For this purpose, a series of configurations in a cactus should be dealt with.

signed star domination, cactus, graph configuration, algorithm.