On Signed Star Domination in Graphs

For a graph G = (V, E) without isolated vertex, a function f: E(G) {-1, 1} is said to be a signed star dominating function of G for every v V(G), where E(v) = {uv} E(G)| u V(G)}. The minimum value of , taken over all signed star dominating functions f of G, is called the signed star domination number of G and is denoted by (ss)(G). This paper studies the bounds and algorithms of signed star domination numbers in some classes of graphs. In particular, sharp bounds for the signed star domination number of a general graph and a linear-time algorithm for the signed star domination problem in a tree is presented.