MATEMATIQKI VESNIK

59 (2007), 171–179

UDK 519.175

originalni nauqni rad research paper

FORCING SIGNED DOMINATION NUMBERS IN GRAPHS

S. M. Sheikholeslami

Abstract. We initiate the study of forcing signed domination in graphs. A function f : V (G) ⟶ {−1, +1} is called signed dominating function if for each v ∈ V (G), ∑_{u∈N[v]}f(u) ≥ 1. For a signed dominating function f of G, the weight f is w(f) = ∑_{v∈V} f(v). The signed domination number γ_{s}(G) is the minimum weight of a signed dominating function on G. A signed dominating function of weight γ_{s}(G) is called a γ_{s}(G)-function. A γ_{s}(G)-function f can also be represented by a set of ordered pairs S_{f} = {(v, f(v)) : v ∈ V }. A subset T of S_{f} is called a forcing subset of S_{f} if S_{f} is the unique extension of T to a γ_{s}(G)-function. The forcing signed domination number of S_{f}, f(S_{f} , γ_{s}), is defined by f(S_{f} , γ_{s}) = min{|T | : T is a forcing subset of S_{f} } and the forcing signed domination number of G, f(G, γ_{s}), is defined by f(G, γ_{s}) = min{f(S_{f} , γ_{s}) : S_{f} is a γ_{s}(G)-function}. For every graph G, f(G, γ_{s}) ≥ 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, γ_{s}) = a and γ_{s}(G) = b. The forcing signed domination number of several classes of graph, including paths, cycles, Dutch-windmills, wheels, ladders and prisms are determined.

1. Introduction

Let G a be graph with vertex set V (G). For every vertex v ∈ V (G), the open neighborhood N(v) is the set {u ∈ V (G) | uv ∈ E(G)} and its closed neighborhood is N[v] = N(v) ∪ {v}. For a function f : V (G) ⟶ {−1, 1} and a subset S of V (G) we define f(S) = ∑_{u∈S} f(u). If S = N[v] for some v ∈ V, then we denote f(S) by f[v]. For a function f : V (G) ⟶ R, the weight f is w(f) = ∑_{v∈V} f(v). A signed dominating function of G is a function f : V (G) ⟶ {+1, −1} such that f[v] ≥ 1 for all v ∈ V. The signed domination number γ_{s}(G) is the minimum weight of a signed dominating function on G. A signed dominating function of weight γ_{s}(G) is defined a γ_{s}(G)-function. For every graph G, we have γ_{s}(G) ∈ Z. The signed domination number was introduced by Dunbar et al. in [2] and since then many results have also been obtained on the parameter γ_{s}(G) (see for instance [3, 4, 8, 9, 11, 13]. We use [12] for terminology and notation which are not defined here.

A signed dominating function f of G can also be represented by a set of ordered pairs S_{f} = {(v, f(v)) | v ∈ V }. Let f be a γ_{s}(G)-function. A subset T of S_{f} is called a forcing subset of S_{f} if S_{f} is the unique extension of T to a γ_{s}(G)-

AMS Subject Classification: 05C15

Keywords and phrases: Forcing signed domination number, signed domination number.

function. The forcing signed domination number of S_{f}, f(S_{f}, γ_{s}), is defined by f(S_{f}, γ_{s}) = min{|T | : T is a forcing subset of S_{f}}. The forcing signed domination number f(G, γ_{s}) is defined by f(G, γ_{s}) = min{f(S_{f}, γ_{s}) | S_{f} is a γ_{s}(G)-function}. Hence for every graph G, f(G, γ_{s}) ≥ 0.

The concept of forcing numbers has been studied in different areas of combinatorics and graph theory, including the chromatic numbers [10], domination numbers [1, 6] and semi-H-cordial labeling of a graph [7]. In this paper we initiate the study of forcing signed domination numbers in graphs. The paper is organized as follows: In Section 2, we give some preliminary results for f(G, γ_{s}). We also prove that for every two integer a, b of which a is positive, there exists a simple connected graph G such that f(G, γ_{s}) = a and γ_{s}(G) = b. In section 3, we find the forcing signed domination number of paths and cycles. In Section 4, we determine the forcing signed domination number of Dutch-windmill graphs and wheels. Section 5 is devoted to determine the forcing signed domination number of ladders and prisms.

Here are some well-known results on γ_{s}(G).

Theorem A. [2] If f is a signed dominating function for a graph G, then each endvertex and each vertex adjacent with an endvertex of G is assigned the value 1 under f.

Theorem B. [5] For n ≥ 2, γ_{s}(P_{n}) = n − 2⌊\frac{n−2}{3}⌋. Theorem C. [5] For n ≥ 3, γ_{s}(C_{n}) = n − 2⌊\frac{n}{3}⌋. Theorem D. [8] For n ≥ 2,

γ_{s}(P_{2} × P_{n}) = \{ \begin{matrix}n & if n is even; \\ n − 1 & if n is odd. \end{matrix}

Theorem E. [8] For n ≥ 3,

γ_{s}(P_{2} × C_{n}) = \{ \begin{matrix}n & if n ≡ 0 (mod 4); \\ n + 2 & if n ≡ 2 (mod 4); \\ n + 1 & if n is odd. \end{matrix}

2. Realizability

We have already noted that if G is a graph with f(G, γ_{s}) = a and γ_{s}(G) = b, then a ≥ 0 and b ∈ Z. In this section we prove the corresponding realization result.

The following observations will be useful in this note.

Observation 1. Let G be a graph with Δ ≤ 3, g be a signed dominating function of G and u, v ∈ V (G). If g(u) = g(v) = −1, then d(u, v) ≥ 3.

Observation 2. For a graph G, f(G, γ_{s}) = 0 if and only if G has a unique γ_{s}(G)-function. Moreover, f(G, γ_{s}) = 1 if and only if G does not have a unique γ_{s}(G)-function but some pair (v, ±1) belongs to exactly one γ_{s}(G)-function.

The following result is a direct consequence of Observation 2

Corollary 3. For a graph G, f(G, γ_{s}) > 1 if and only if every pair (v, ±1) of each γ_{s}(G)-function belongs to at least two γ_{s}(G)-functions.

Theorem 4. For every graph G of order n, if γ_{s}(G) = n then f(G, γ_{s}) = 0.

Proof. Let γ_{s}(G) = n. We show that every non isolated vertex is either an endvertex or adjacent to an endvertex. Consider a vertex v that is neither an endvertex nor adjacent to an endvertex. Then we can assign −1 to v and +1 to each other vertex, to produce a signed dominating function on G of weight n − 2, which is a contradiction. This proves our claim and the theorem is true by Theorem A.

Corollary 5. For n ≥ 1, f(K_{1,n}, γ_{s}) = 0.

Proof. By Theorem A, γ_{s}(K_{1,n}) = n and the result follows by Theorem 4. Next theorem shows that for every pair a, b of integers, with a positive, there

exists a simple connected graph G such that f(G, γ_{s}) = a and γ_{s}(G) = b.

Theorem 6. For every two integers a and b, with a positive, there exists a simple connected graph G such that a = f(G, γ_{s}) and b = γ_{s}(G).

Proof. Let G be obtained from complete graph K_{8|b|+8} whose vertex set is {v_{1}, …, v_{8|b|+8}}, by adding 24|b| + 24 new vertices, say u_{1}, u_{2}, …, u_{8|b|+8}, w_{1}, w_{2}, …, w_{8|b|+8}, z_{1}, z_{2}, …, z_{8|b|+8} and new edges u_{i}v_{i}, v_{1}w_{i}, v_{2}w_{i}, v_{3}z_{i}, v_{4}z_{i} for each i. We consider three cases.

Case 1. b = 0. Obviously f(G, γ_{s}) = γ_{s}(G) = 0. Suppose now that a > 0. Let G_{1} be obtained from G by adding 2a new vertices, say m_{i}, n_{i} (1 ≤ i ≤ a), and new edges v_{8|b|+8}m_{i}, v_{8|b|+8}n_{i} and m_{i}n_{i} for i = 1, …, a. It is easy to see that f(G_{1}, γ_{s}) = a and γ_{s}(G_{1}) = 0.

Case 2. b > 0. First let a = 0. Let G_{2} be obtained from G by adding b pendant edges at v_{8|b|+8}, say v_{8|b|+8}y_{1}, …, v_{8|b|+8}y_{b}. It is easy to see that γ_{s}(G_{2}) = b and f(G_{2}, γ_{s}) = 0. Suppose now that a > 0. Let G_{3} be obtained from G_{2} by adding 2a new vertices m_{i}, n_{i} (1 ≤ i ≤ a) and new edges v_{8|b|+8}m_{i}, v_{8|b|+8}n_{i} and m_{i}n_{i} for i = 1, …, a. One can see that f(G_{3}, γ_{s}) = a and γ_{s}(G_{3}) = b.

Case 3. b < 0. If a = 0, then let G_{4} be obtained from G by adding |b| new vertices, say y_{1}, …, y_{|b|}, and joining them to both v_{5}, v_{6}. Obviously f(G_{4}, γ_{s}) = 0 and γ_{s}(G_{4}) = b. If a > 0, then let G_{5} be obtained from G_{4} by adding 2a new vertices m_{i}, n_{i} (1 ≤ i ≤ a) and adding new edges v_{8|b|+8}m_{i}, v_{8|b|+8}n_{i} and m_{i}n_{i} for i = 1, …, a. It is easy to verify that f(G_{5}, γ_{s}) = a and γ_{s}(G_{5}) = b. This completes the proof.

3. Forcing signed domination number of paths and cycles

In this section we determine the forcing signed domination number of paths and cycles. We begin with the forcing signed domination number of paths. Since for 1 ≤ n ≤ 4, f(P_{n}, γ_{s}) = 0 by Theorem A, we consider paths of order at least 5.

Theorem 7. For n ≥ 5,

f(P_{n}, γ_{s}) = \{ \begin{matrix}0 & if n ≡ 2 (mod 3); \\ 1 & if n ≡ 0 or 1 (mod 3). \end{matrix}

Proof. Let P_{n} = v_{1}, v_{2}, …, v_{n} and g be a γ_{s}-function of P_{n}. By Theorem A, g(v_{1}) = g(v_{2}) = g(v_{n}) = g(v_{n−1}) = 1. By Observation 1, g(v_{i}) = g(v_{j}) = −1 implies that |i − j| ≥ 3. Therefore, the number of vertices of P_{n} which g can assign −1 to them is at most ⌊\frac{n−2}{3}⌋. On the other hand, g must assign the value −1 to exactly ⌊\frac{n−2}{3}⌋ vertices of P_{n} by Theorem B. If n = 3k + 2 for some k ∈ N, then obviously g(v_{3i}) = −1 for i = 1, …, k and g assigns the value 1 to each other vertex. Thus f(P_{3k+2}, γ_{s}) = 0.

Now let n ≢ 2 (mod 3). Define g, h : V (P_{n}) ⟶ {−1, +1} by

g(v_{i}) = \{ \begin{matrix}−1 & if i = 3, 6, …, 3(⌊\frac{n}{3}⌋ − 1); \\ 1 & otherwise, \end{matrix}

and

h(v_{i}) = \{ \begin{matrix}−1 & if i = 4, 7, …, 3(⌊\frac{n}{3}⌋ − 1) + 1; \\ 1 & otherwise . \end{matrix}

It is easy to see that g and h are γ_{s}(P_{n})-function. It follows that f(P_{n}, γ_{s}) ≥ 1 by Observation 2. Consider two cases.

Case 1. n ≡ 0 (mod 3). Let T = {(v_{n−2}, 1)}. We claim that T is a forcing subset for g. Let f be a γ_{s}(P_{n})-function such that f(v_{n−2}) = 1. This forces f(v_{3i}) = −1 for 1 ≤ i ≤ \frac{n}{3} − 1, which implies f assigns the value 1 to each other vertex. Therefore f = g and f(S_{g}, γ_{s}) ≤ 1. Thus, f(P_{n}, γ_{s}) ≤ 1.

Case 2. n ≡ 1 (mod 3). We show that T = {(v_{n−4}, −1)} is a forcing subset of g. Let f be a γ_{s}(P_{n})-function such that f(v_{n−4}) = −1. This forces f(v_{n−3}) = f(v_{n−2}) = f(v_{n−5}) = f(v_{n−6}) = 1 by Theorem A and Observation 1. Since f must assign the value −1 exactly to ⌊\frac{n−2}{3}⌋ vertices of P_{n} by Theorem B, we must have f(v_{3}) = f(v_{6}) = … = f(v_{n−4}) = −1. It follows that f must assign the value 1 to each other vertex. Thus f = g and f(S_{g}, γ_{s}) ≤ 1. Therefore f(P_{n}, γ_{s}) ≤ 1 and the proof is complete.

Next we determine f(C_{n}, γ_{s}) for all cycles. Obviously, f(C_{n}, γ_{s}) = 1 when n = 3, 4, 5. Therefore, we consider cycles of order at least 6.

Theorem 8. For n ≥ 6,

f(C_{n}, γ_{s}) = \{ \begin{matrix}1 & if n ≡ 0 (mod 3); \\ 2 & if n ≡ 1 or 2 (mod 3). \end{matrix}

Proof. Let C_{n} = v_{1}, v_{2}, …, v_{n}. By Theorem C, γ_{s}(C_{n}) = n − 2⌊\frac{n}{3}⌋. Define g, h : V (C_{n}) ⟶ {−1, +1} by

g(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 4, …, 3(⌊\frac{n}{3}⌋ − 1) + 1; \\ 1 & otherwise, \end{matrix}

and

h(v_{i}) = \{ \begin{matrix}−1 & if i = 2, 5, …, 3(⌊\frac{n}{3}⌋ − 1) + 2; \\ 1 & otherwise . \end{matrix}

It is easy to see that g and h are γ_{s}(C_{n})-function. It follows that f(C_{n}, γ_{s}) ≥ 1 by Observation 2. First let n ≡ 0 (mod 3). We claim that T = {(v_{1}, −1)} is a forcing subset for g. Let f be an extension of T to a γ_{s}(C_{n})-function. This forces f(v_{2}) = f(v_{3}) = f(v_{n}) = f(v_{n−1}) = 1 by Observation 1. Since f is a γ_{s}(C_{n})- function, f must assign the value −1 to exactly ⌊\frac{n}{3}⌋ vertices of C_{n} by Theorem C. This forces f(v_{4}) = f(v_{7}) = … = f(v_{n−2}) = −1. It follows that f assigns the value 1 to each other vertex of C_{n}. Therefore f = g and f(C_{n}, γ_{s}) ≤ 1.

Now let n ≡ 1 (mod 3). Then n = 3k + 1 for some k ≥ 2. First we show that every set T = {(v, ε) | v ∈ V (C_{n}) and ε = +1 or − 1} which has an extension to a γ_{s}(C_{n})-function, has at least two extension to a γ_{s}(C_{n})-function which implies f(C_{n}, γ_{s}) ≥ 2. Without loss of generality, we can assume v = v_{1} and ε = −1. Define g, h : V (C_{n}) ⟶ {−1, +1} by

g(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 4, …, 3(k − 1) + 1; \\ 1 & otherwise, \end{matrix}

and

h(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 5, …, 3(k − 1) + 2; \\ 1 & otherwise . \end{matrix}

It is easy to see that g and h are γ_{s}(C_{n})-function such that g(v_{1}) = h(v_{1}) = −1. It follows that f(C_{n}, γ_{s}) ≥ 2 by Corollary 3. Now it is easy to verify that T = {(v_{1}, −1), (v_{n−2}, 1)} is a forcing subset of g which implies f(C_{n}, γ_{s}) ≤ 2. Thus f(C_{n}, γ_{s}) = 2.

If n ≡ 2 (mod 3), then an argument similar to that described in case n ≡ 1 (mod 3) shows that f(C_{n}, γ_{s}) = 2. This completes the proof.

4. The Dutch-windmill graphs and wheels

The Dutch-windmill graph, K_{3}^{(m)}, is a graph which consists of m copies of K_{3} with a vertex in common. The wheel, W_{n}, is a graph with n + 1 vertices {v_{0}, v_{1}, …, v_{n}} and edges {v_{0}v_{i} | 1 ≤ i ≤ n} ∪ {v_{1}v_{2}, v_{2}v_{3}, …, v_{n−1}v_{n}, v_{n}v_{1}}. In this section we find the forcing signed domination number of K_{3}^{(m)} and W_{n}.

Lemma 9. For every positive integer m, γ_{s}(K_{3}^{(m)}) = 1.

Proof. By Theorem C, we may assume m ≥ 2. Let v, u_{i}, w_{i} are the vertices of the i-th copy of K_{3} in K_{3}^{(m)} (v is the common vertex). Define g : V (K_{3}^{(m)}) ⟶ {−1, +1} by

g(w) = \{ \begin{matrix}1 & if w = v, w_{i} and 1 ≤ i ≤ m; \\ −1 & if w = u_{i} and 1 ≤ i ≤ m. \end{matrix}

Obviously g is a signed dominating function for K_{3}^{(m)}. Thus, γ_{s}(K_{3}^{(m)}) ≤ 1. Now let h be a γ_{s}-function of K_{3}^{(m)}. Then h(v) = 1, for otherwise h must assign the value +1 to each other vertex which leads to γ_{s}(h) = 2m − 1 > 1, a contradiction. Now h can assign the value −1 to exactly one of the vertices w_{i} or v_{i} for each i. Thus, w(h) ≥ 1 and γ_{s}(K_{3}^{(m)}) = 1.

Theorem 10. For every positive integer m, f(K_{3}^{(m)}, γ_{s}) = m.

Proof. Let g be the γ_{s}-function of K_{3}^{(m)} defined in Lemma 9. It is easy to see that T = {(u_{i}, −1) | 1 ≤ i ≤ m} is a forcing subset of g. Therefore, f(K_{3}^{(m)}, γ_{s}) ≤ m. Now we show that f(K_{3}^{(m)}, γ_{s}) ≥ m. Let S = {(w, ε_{w}) | w ∈ V (K_{3}^{(m)}) and ε_{w} = +1 or -1} where |S| < m and S has at least an extension to a γ_{s}-function of K_{3}^{(m)}. Without loss of generality we may assume S does not intersect the first copy of K_{3}. Define S_{1} = S ∪ {(w_{1}, 1), (u_{1}, −1)} and S_{2} = S ∪ {(w_{1}, −1), (u_{1}, 1)}. Now we can extend S_{1} and S_{2}, to a γ_{s}-function of K_{3}^{(m)}. It follows that S is not a forcing subset for any γ_{s}-function of K_{3}^{(m)}. Thus, f(K_{3}^{(m)}, γ_{s}) ≥ m and the proof is complete.

Since γ_{s}(W_{3}) = 2 and γ_{s}(W_{4}) = 3, we consider W_{n} with n ≥ 5.

Lemma 11. For n ≥ 5, γ_{s}(W_{n}) = n + 1 − 2⌊\frac{n}{3}⌋.
Proof. Define g : W_{n} ⟶ {−1, +1} by

g(w) = \{ \begin{matrix}−1 & if w = v_{3i+1} and 0 ≤ i ≤ ⌊\frac{n}{3}⌋ − 1; \\ 1 & otherwise . \end{matrix}

Obviously g is a signed dominating function for W_{n} which implies γ_{s}(W_{n}) ≤ n + 1 − 2⌊\frac{n}{3}⌋. Now let h be a γ_{s}-function of W_{n}. We claim that h(v_{0}) = 1. Let, to the contrary, h(v_{0}) = −1. Since deg(v_{i}) = 3 for each i, h must assign the value +1 to each other vertex which implies γ_{s}(h) = n − 1 > n + 1 − 2⌊\frac{n}{3}⌋, a contradiction. Therefore h(v_{0}) = 1. Since deg(v_{i}) ≤ 3 for each i ≥ 1, h(v_{i}) = h(v_{j}) = −1 implies that |i−j| ≥ 3 by Observation 1. It follows that |\{w ∈ V (W_{n}) : h(w) = −1\}| ≤ ⌊\frac{n}{3}⌋. Thus γ_{s}(W_{n}) = w(h) ≥ n + 1 − 2⌊\frac{n}{3}⌋ and the proof is complete.

It is easy to see that f(W_{n}, γ_{s}) = 1 when n = 3, 4, 5. Therefore, we assume n ≥ 6.

Theorem 12. For n ≥ 6,

f(W_{n}, γ_{s}) = \{ \begin{matrix}1 & if n ≡ 0 (mod 3); \\ 2 & otherwise . \end{matrix}

Proof. First let n ≡ 0 (mod 3). Define g, h : V (W_{n}) ⟶ {−1, +1} by

g(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 4, …, 3(⌊\frac{n}{3}⌋ − 1) + 1; \\ 1 & otherwise, \end{matrix}

and

h(v_{i}) = \{ \begin{matrix}−1 & if i = 2, 5, …, 3(⌊\frac{n}{3}⌋ − 1) + 2; \\ 1 & otherwise . \end{matrix}

Obviously g and h are signed dominating function for W_{n}. By Lemma 11, g and h are γ_{s}(W_{n})-functions. It follows that f(W_{n}, γ_{s}) ≥ 1 by Observation 2. It is easy to verify that T = {(v_{1}, −1)} is a forcing subset for g which impliesf(W_{n}, γ_{s}) = 1.

Now let n ≢ 0 (mod 3). Let T = {(v, ε) | v ∈ V (W_{n}) and ε = +1 or − 1} and T has an extension to a γ_{s}(W_{n})-function. If i = 0 or ε = +1, then obviously T has at least two extension to a γ_{s}(W_{n})-function. Suppose now that i ≠ 0 and ε = −1. Without loss of generality we may assume v = v_{1}. Define g^{∗}, h^{∗} : V (W_{n}) ⟶ {−1, +1} by

g^{∗}(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 4, …, 3(⌊\frac{n}{3}⌋ − 1) + 1; \\ 1 & otherwise, \end{matrix}

and

h^{∗}(v_{i}) = \{ \begin{matrix}−1 & if i = 1, 5, …, 3(⌊\frac{n}{3}⌋ − 1) + 2; \\ 1 & otherwise . \end{matrix}

Obviously g^{∗} and h^{∗} are signed dominating functions for which g(v_{1}) = h(v_{1}) = −1 and by Lemma 11, g^{∗} and h^{∗} are γ_{s}(W_{n})-functions. It follows that f(W_{n}, γ_{s}) ≥ 2 by Corollary 3. It is straightforward to see that T_{1} = {(v_{1}, −1), (v_{n−2}, 1)} if n ≡ 1 (mod 3) and T_{2} = {(v_{1}, −1), (v_{n−4}, −1)} when n ≡ 2 (mod 3), is a forcing subset of g^{∗} which implies f(W_{n}, γ_{s}) ≤ 2. Thus f(W_{n}, γ_{s}) = 2 and the proof is complete.

5. Ladders and Prisms

In this section we find the forcing signed domination number of ladders and prisms. Throughout this section we assume the vertices of the i-th copy of P_{2} in ladders P_{2} × P_{n} (prisms P_{2} × C_{n}) are u_{i}, v_{i} for i = 1, 2, …, n. (see Figure 1).

Fig. 1. Ladders P_{2} × P_{n}
Since P_{2} × P_{2} = C_{4}, f(P_{2} × P_{2}, γ_{s}) = 1. We assume n ≥ 3.
Theorem 13. For n ≥ 3, f(P_{2} × P_{n}, γ_{s}) = 1.
Proof. Define g, h : V (P_{2} × P_{n}) ⟶ {−1, +1} by

g(w) = \{ \begin{matrix}−1 & if w = u_{4i+1} and 0 ≤ i ≤ ⌈\frac{n}{4}⌉ − 1; \\ −1 & if w = v_{4i+3} and 0 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1; \\ 1 & otherwise, \end{matrix}

and h(u_{i}) = g(v_{i}) and h(v_{i}) = g(u_{i}) for each i. It is easy to see that g and h are γ_{s}-functions for P_{2} × P_{n} by Theorem D. It follows that f(P_{2} × P_{n}, γ_{s}) ≥ 1 by Observation 2. Let g be the γ_{s}-function defined above. Let M = {w ∈ V (P_{2} ×P_{n}) | g(w) = −1}. Consider two cases.

Case 1. n is odd. By Theorem D, |M| = \frac{n+1}{2}. Now we show that T = {(u_{1}, −1)} is a forcing subset for g. Let f be an extension of T to a γ_{s}(P_{2} × P_{n})- function. By Observation 1, f(v_{1}) = f(u_{2}) = f(v_{2}) = f(u_{3}) = 1 and |M ∩ \{u_{i}, v_{i}, u_{i−1}, v_{i−1}, u_{i+1}, v_{i+1}\}| ≤ 1 for each i. Since |M| = \frac{n+1}{2}, f(v_{3}) = −1. An inductive argument shows that f(u_{4i+1}) = −1 for 0 ≤ i ≤ ⌈\frac{n}{4}⌉ − 1, f(v_{4i+3}) = −1 for 0 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1 and f assigns the value +1 to each other vertex. Thus, f = g and f(P_{2} × P_{n}, γ_{s}) ≤ f(S_{g}, γ_{s}) ≤ 1.

Case 2. n is even. An argument similar to that described in case 1, proves that T_{1} = {(v_{n−1}, −1)} and T_{2} = {(u_{n−1}, −1)} are forcing subsets of g when 4|n and 4 ∤ n, respectively. It follows that f(P_{2} ×P_{n}, γ_{s}) ≤ f(S_{g}, γ_{s}) ≤ 1 and the proof is complete.

Finally, we determine f(P_{2} × C_{n}, γ_{s}) for n ≥ 3. Since f(P_{2} × C_{n}, γ_{s}) = 1 when n is 3 and 4, we assume n ≥ 5.

Theorem 14. For n ≥ 5,

f(P_{2} × C_{n}, γ_{s}) = \{ \begin{matrix}1 & if n ≡ 0 (mod 4); \\ 2 & otherwise . \end{matrix}

Proof. First let n ≡ 0 (mod 4). Define g, h : V (P_{2} × C_{n}) ⟶ {−1, +1} by

g(w) = \{ \begin{matrix}−1 & if w = u_{4i+1}, v_{4i+3} and 0 ≤ i ≤ ⌊\frac{n}{4}⌋ − 1; \\ 1 & otherwise, \end{matrix}

and h(u_{i}) = g(v_{i}) and h(v_{i}) = g(u_{i}) for each i. Obviously g and h are signed dominating functions for P_{2} × C_{n}. Therefore, g and h are γ_{s}(P_{2} × C_{n})-functions by Theorem E. It follows that f(P_{2} × C_{n}, γ_{s}) ≥ 1 by Observation 2. An argument similar to that described in the Theorem 13, shows that T = {(v_{n−1}, −1)} is a forcing subset for g. Thus f(P_{2} × C_{n}, γ_{s}) = 1.

Now let n ≢ 0 (mod 4). First we show that f(P_{2} × C_{n}, γ_{s}) ≥ 2. In order to do this, it is sufficient to show that every set T = {(w, ε_{w}) | w ∈ V (P_{2} × C_{n}), ε_{w} = +1 or − 1} which has at least one extension to a γ_{s}-function, has two extensions to a γ_{s}-function for P_{2} × C_{n}. Without loss of generality, we may assume w = u_{1} and ε = −1. Define g, h : V (P_{2} × C_{n}) ⟶ {−1, +1} by

g(w) = \{ \begin{matrix}−1 & if w = u_{4i+1} and 0 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1; \\ −1 & if w = v_{4i+3} and 0 ≤ i ≤ ⌊\frac{n}{4}⌋ − 1; \\ 1 & otherwise, \end{matrix}

and

h(w) = \{ \begin{matrix}−1 & if w = u_{1}, u_{4i+4} and 0 ≤ i ≤ ⌊\frac{n}{4}⌋ − 1; \\ −1 & if w = v_{4i+2} and 1 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1; \\ 1 & otherwise, \end{matrix}

if n ≡ 3 (mod 4), and

h(w) = \{ \begin{matrix}−1 & if w = u_{1}, u_{4i+2}, 1 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1 and ⌊\frac{n+1}{4}⌋ ≥ 2; \\ −1 & if w = v_{4i+4}, 0 ≤ i ≤ ⌊\frac{n}{4}⌋ − 1; \\ 1 & otherwise, \end{matrix}

when n ≡ 1 or 2 (mod 4). Obviously g, h are signed dominating functions for P_{2} × C_{n} in each case and by Theorem E, g and h are γ_{s}(P_{2} × C_{n})-functions. It follows that f(P_{2} × C_{n}, γ_{s}) ≥ 2 by Corollary 3. Now we show that T_{1} = {(u_{1}, −1), (u_{n−2}, −1)} if n ≡ 3 (mod 4), T_{2} = {(u_{1}, −1), (v_{n−3}, −1)} if n ≡ 1 (mod 4) and T_{3} = {(u_{1}, −1), (v_{n−2}, −1)} when n ≡ 2 (mod 4), is a forcing subset for g.

Let f be an extension of T_{1} to a γ_{s}-function for P_{2} × C_{n}. By Observation 1, if f(u) = f(v) = −1, then d(u, v) ≥ 3 which implies f(v_{1}) = f(u_{2}) = f(v_{2}) = f(u_{3}) = f(u_{n}) = f(v_{n}) = f(u_{n−1}) = f(v_{n−1}) = f(v_{n−2}) = f(u_{n−3}) = f(v_{n−3}) = f(u_{n−4}) = 1. Since |\{w ∈ V (P_{2} ×C_{n}) | f(w) = −1\}| = \frac{n−1}{2}, an inductive argument shows that f(u_{4i+1}) = −1 for 0 ≤ i ≤ ⌊\frac{n+1}{4}⌋ − 1, f(v_{4i+3}) = −1 for 0 ≤ i ≤ ⌊\frac{n}{4}⌋ − 1 and f assigns +1 to each other vertex. Thus f = g and f(P_{2} ×C_{n}, γ_{s}) ≤ 2. Now an argument similar to that described for T_{1} may be applied to show that T_{2} and T_{3} are forcing subset for g. Thus f(P_{2} × C_{n}, γ_{s}) = 2 and the proof is complete.

REFERENCES

[1] G. Chartrand, H. Gavlas, R. C. Vandell and F. Harary, The forcing domination number of a graph, J. Combin. Math. Combin. Comput. 25 (1997), 161–174.

[2] J.E. Dunbar, S.T. Hedetniemi, M.A. Henning, and P.J. Slater, Signed domination in graphs, Graph Theory, Combinatorics and Application, John Wiley & Sons, Inc. 1 (1995), 311–322.

[3] O. Favaron, Signed domination in regular graphs, Discrete Math. 158 (1996), 287–293.

[4] Z. Füredi and D. Mubayi, Signed domination in regular graphs and set-systems, Journal of Combinatorial Theory, Series B, 76 (1999), 223–239.

[5] T.W. Haynes, S.T. Hedetniemi, and P.J. Slater, Domination in Graphs: Advanced Topics, Marcel Dekker Inc.

[6] A. Khodkar and S.M. Sheikholeslami, The forcing domination number of some graphs, Ars Combinnatoria 82 (2007), 365–372.

[7] R. Khoeilar, S.M. Sheikholeslami, and A. Khodkar, The forcing semi H- cordial numbers of certain graphs, J. Combin. Math. Combin. Comput. 59 (2006), 151–164.

[8] R. Hass and T.B. Wexler, Bounds on the signed domination number of a graph, Discrete Math. 195 (1999), 295–298.

[9] R. Hass and T.B. Wexler, Signed domination numbers of a graph and its complement, Discrete Math. 283 (2004), 87–92.

[10] S.E. Mahmoodian, R. Naserasr and M. Zaker, Defining sets in vertex colorings of graphs and Latin rectangles, Discrete Math. 167 (1997), 451–460.

[11] L. Volkmann and B. Zelinka, Signed domatic number of a graph, Discrete Applied Math. 150 (2005), 261–267.

[12] D.B. West, Introduction to Graph Theory, Prentice-Hall, Inc, 2000.

[13] Z. Zhang, B. Xu, Y. Li, and L. Liu, A note on the lower bound of signed domination number of a graph, Discrete Math. 195 (1999), 295–298.

(received 23.03.2007, in revised form 30.07.2007)

Department of Mathematics, Azarbaijan University of Tarbiat Moallem, Tabriz, I.R. Iran

E-mail: s.m.sheikholeslami@azaruniv.edu