Forcing signed domination numbers in graphs

Abstract

We initiate the study of forcing signed domination in graphs. Afunction $f:V(G)\longrightarrow \{-1,+1\}$ is called {ıt signeddominating function} if for each $vın V(G)$, ${ßsize\sum}_{uınN[v]}f(u)\geq 1$. For a signed dominating function $f$ of $G$, the{ıt weight} $f$ is $w(f)={ßsize\sum}_{vın V}f(v)$. The {ıt signeddomination number} $\gamma_s(G)$ is the minimum weight of a signeddominating function on $G$. A signed dominating function of weight$\gamma_s(G)$ is called a $\gamma_s(G)$-{ıt function}. A$\gamma_s(G)$-function $f$ can also be represented by a set ofordered pairs $S_f=\{(v, f(v)): vın V\}$. A subset $T$ of $S_f$ iscalled a {ıt forcing subset\/} of $S_f$ if $S_f$ is the uniqueextension of $T$ to a $\gamma_s(G)$-function. The {ıt forcingsigned domination number} of $S_f$, $f(S_f,{\gamma_s})$, is definedby $f(S_f,{\gamma_s})=\min\{|T|: \mbox{$T$ is a forcing subset of\/ }S_f\}$ and the {ıt forcing signed domination number} of $G$,$f(G,{\gamma_s})$, is defined by$f(G,{\gamma_s})=\min\{f(S_f,{\gamma_s}): S_f \;\;\tx{is a}\;\gamma_s(G)\mbox{-function}\}$. For every graph $G$,$f(G,\gamma_s)\geq 0$. In this paper we show that for integer $a,b$with $a$ positive, there exists a simple connected graph $G$ suchthat $f(G,\gamma_s)=a$ and $\gamma_s(G)=b$. The forcing signeddomination number of several classes of graph, including paths,cycles, Dutch-windmills, wheels, ladders and prisms are determined.