Abstract

We initiate the study of forcing signed domination in graphs. A function $f:V(G)\longrightarrow \{-1,+1\}$ is called {\it signed dominating function} if for each $v\in V(G)$, ${ßsize\sum}_{u\in N[v]}f(u)\geq 1$. For a signed dominating function $f$ of $G$, the {\it weight} $f$ is $w(f)={ßsize\sum}_{v\in V}f(v)$. The {\it signed domination number} $\gamma_s(G)$ is the minimum weight of a signed dominating function on $G$. A signed dominating function of weight $\gamma_s(G)$ is called a $\gamma_s(G)$-{\it function}. A $\gamma_s(G)$-function $f$ can also be represented by a set of ordered pairs $S_f=\{(v, f(v)): v\in V\}$. A subset $T$ of $S_f$ is called a {\it forcing subset\/} of $S_f$ if $S_f$ is the unique extension of $T$ to a $\gamma_s(G)$-function. The {\it forcing signed domination number} of $S_f$, $f(S_f,{\gamma_s})$, is defined by $f(S_f,{\gamma_s})=\min\{|T|: \mbox{$T$ is a forcing subset of\/ } S_f\}$ and the {\it 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$ such that $f(G,\gamma_s)=a$ and $\gamma_s(G)=b$. The forcing signed domination number of several classes of graph, including paths, cycles, Dutch-windmills, wheels, ladders and prisms are determined.

Keywords: Forcing signed domination number, signed domination number.

MSC: 05C15

Pages:  171--179     

Volume  59 ,  Issue  4 ,  2007