Received 21 March 2015; accepted 21 July 2015; published 24 July 2015

ABSTRACT

Let D be a finite simple directed graph with vertex set V(D) and arc set A(D). A function is called a signed dominating function (SDF) if for each vertex. The weight of f is defined by. The signed domination number of a digraph D is. Let C_m × C_n denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of g_s(C_m × C_n) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of g_s(C_m × C_n) when m, (mod 3) and bounds for otherwise.

Keywords:

Directed Graph, Directed Cycle, Cartesian Product, Signed Dominating Function, Signed Domination Number

1. Introduction

Throughout this paper, a digraph always means a finite directed graph without loops and multiple arcs, where is the vertex set and is the arc set. If uv is an arc of D, then say that v is an out-neighbor of u and u is an in-neighbor of v. For a vertex, let and denote the set of out-neighbors and in-neighbors of v, respectively. We write and for the out-degree and in-degree of v in D, respectively (shortly,). A digraph D is r-regular if for any vertex. Let and. The maximum out-degree and in-degree of D are denoted by and, respectively (shortly D⁺, D⁻). The minimum out-degree and in-degree of D are denoted by and, respectively (shortly,). A signed dominating function of D is defined in [1] as function such that for every vertex. The signed domination number of a directed graph D is . Also, a signed k-dominating function (SKDF) of D is a function

such that for every vertex. The k-signed domination number of a di-

graph D is. Consult [2] for the notation and terminology which are not defined here.

The Cartesian product of two digraphs D₁ and D₂ is the digraph with vertex set and if and only if either and or and.

In the past few years, several types of domination problems in graphs had been studied [3] -[7] , most of those belonging to the vertex domination. In 1995, Dunbar et al. [3] , had introduced the concept of signed domination number of an undirected graph. Haas and Wexler in [1] , established a sharp lower bound on the signed domination number of a general graph with a given minimum and maximum degree and also of some simple grid graph. Zelinka [8] initiated the study of the signed domination numbers of digraphs. He studied the signed domination number of digraphs for which the in-degrees did not exceed 1, as well as for acyclic tournaments and the circulant tournaments. Karami et al. [9] established lower and upper bounds for the signed domination number of digraphs. Atapour et al. [10] presented some sharp lower bounds on the signed k-domination number of digraphs. Shaheen and Salim in [11] , were studied the signed domination number of two directed cycles C_m ´ C_n when m = 3, 4, 5, 6, 7 and arbitrary n. In this paper, we study the Cartesian product of two directed cycles C_m and C_n for mn ≥ 8n. We mainly determine the exact values of, , and for some values of m and n. Some previous results:

Theorem 1.1 (Zelinka [8] ). Let D be a directed cycle or path with n vertices. Then.

Lemma 1.2 (Zelinka [8] ). Let D be a directed graph with n vertices. Then.

Corollary 1.3 (Karami et al. [9] ). Let D be a directed of order n in which for each

, where k is a nonnegative integer. Then.

In [11] , the following results are proved.

Theorem 1.4 [11] :

, otherwise..

, ,

,.

, otherwise..

2. Main Results

In this section we calculate the signed domination number of the Cartesian product of two directed cycles C_m and C_n for m = 8, 9, 10 and and arbitrary n.

The vertices of a directed cycle C_n are always denoted by theintegers considered modulo n. The ith row of is and the jth column. For any vertex, always we have the indices i and j are reduced modulo m and n, respectively.

Let us introduce a definition. Suppose that f is a signed dominating function for C_m ´ C_n, and assume that. We say that the hth column of is a t-shift of the jth column if for each vertex, where the indices i, t, i + t are reduced modulo m and j, h are reduced modulo n.

Remark 2.1: Let f is a -function. Then for each and each.

Since C_m × C_n is 2-regular, it follows from that because , because and because

. On the other hand, if, and

, then we must have since f is a minimum signed dominating function.

Remark 2.2. Since the case is not possible, we get s_j ≥ 0. Furthermore, s_j is odd if m is odd and even when m is even.

Let f be a signed dominating function for C_m ´ C_n, then we denote of the weight of a

column K_j and put. The sequence is called a signed dominating sequence corresponding to f. We define

Then we have

For the remainder of this section, let f be a signed domination function of C_m × C_n with signed dominating sequence. We need the following Lemma:

Lemma 2.3. If then. Furthermore, and.

Proof. Let, then there are of vertices in K_j which get value −1. By Remark 2.1, include at least of vertices which get the value 1 and at most of vertices which has value −1. Hence,. Furthermore,. By the same argument, we get and. □

Theorem 2.4.

Proof. We define a signed dominating function f as follows:

for and,

for and, and

otherwise. Also we define for.

By the definition of f, we have s_j = 2 for j is odd and s_j = 4 for j is even. Notice, f is a SDF for C₈ × C_n when. Therefore, there is a problem with the vertices of K₁ when.

Now, let us define the following functions:

,

,

We note:

f₁ is a SDF of C₈ × C_n when.

f₂ is a SDF of C₈ × C_n when.

f₃ is a SDF of C₈ × C_n when.

f₄ is a SDF of C₈ × C_n when.

Hence,

(1)

For example, f₁ is a SDF of C₈ × C₁₂, where, see Figure 1.

{Here, we must note that, for simplicity of drawing the Cartesian products of two directed cycles C_m × C_n, we do not draw the arcs from vertices in last column to vertices in first column and the arcs from vertices in last row to vertices in first row. Also for each figure of C_m × C_n, we replace it by a corresponding matrix by signs − and + which descriptions −1 and +1 on figure of, respectively}.

By Remark 2.2, for any minimum signed dominating function f of C₈ × C_n with signed dominating sequence, we have s_j = 0, 2, 4, 6 or 8 for. By Lemma 2.3, if s_j = 0 then, and if s_j = 2 then. This implies that

(2)

(3)

Hence, by (1), (2) and (3) we get

.

.

Assume that.

Let f' ba a signed dominating function with signed dominating sequence.

If m, n ≤ 7, then by Theorem 1.4 is the required (because). Let m, n ≥ 8. We prove the following claim:

Claim 2.1. For k ≥ 2, we have if k is even and when k is odd.

Proof of Claim 2.1. We have the subsequence is including at least two terms. Then, immediately from Remark 2.2 and Lemma 2.3, gets the required. The proof of Claim 2.1 is complete. □

Now, if for some j, then. Without loss of generality, we can assume that. Then Claim 2.1, imply that

(4)

Assume that for all. We have three cases:

Case 1. If for some j. Let. Then from Claim 2.1, we get

(5)

(6)

Case 2. Let. If include at least two terms which are equals 6, then

(7)

For, then 8n is even. By Lemma 1.2, must be even number. Hence, from (7) is

(8)

Assume that for all except once which equals 6. Thus,

(9)

(10)

For the case 3, we need the following claim:

Claim 2.2. Let f' be a minimum signed dominating function of C₈ × C_n with signed dominating sequence.Then for, and up to isomorphism, there is only one possible configuration for f", it is shown in Figure 2. The prove is immediately by drawing. □

Case 3. Let for all. We define

Then we have

Since the case is not possible, we have.

If. Then. Thus

(11)

(12)

If. Then. Hence

(13)

(14)

Let and.

Then we have one possible is as the form. This implies that for and for. By Claim 2.2, we have f' is as the function f, which defined in forefront of Theorem 2.4. However, f is not be a signed dominating function for C₈ × C_n when. Thus

By Lemma 1.2, and above arguments, we conclude that

(15)

(16)

Hence, from (1), (15) and (16), deduce that

Finally, we result that:

□

Theorem 2.5.

Proof. We define a signed dominating function f as follows: for and, and otherwise. Also, let us define the following function:

By define f, we have s_j = 3 for. Notice, f is a SDF for C₉ × C_n for. And f₁ is a SDF of C₉ × C_n for. For an illustration, see Figure 3. Hence,

(17)

(18)

From Corollary 1.3 is. Then by (17), for.

For.

If, then by Theorems 1.4 and 2.4, gets the required. Assume that n ≥ 9.

By Remark 2.2, we have s_j = 1, 3, 5, 7 or 9. By Lemma 2.3, if s_j = 1 then, s_j = 3 then and s_j = 5 then (because if, then we need s_j ≥ 7). By Lemma 2.3, the

cases are not possible. Hence, , for k ≥ 2. This implies that,

(19)

We define

Then we have

If we have one case from the cases X₉ ≥ 1, X₇ ≥ 2, X₅ + X₇ ≥ 2 or X₅ ≥ 3. Then by (19) is.

Assume the contrary, i.e., (X₉ = 0, X₇ < 2, X₅ + X₇ < 2 and X₅ < 3).

Hence,. We consider the cases X₇ < 2 and X₅ < 3, which are including the remained cases, i.e., X₇ = 1 and X₅ = 2. First, we give the following Claim:

Claim 2.3. There is only one possible for is

and

, otherwise for.

The proof comes immediately by the drawing. □

Case 1. X₇ = 1 and X₅ = X₉ = 0. Without loss of generality, we can assume s_n = 7. Then we have the form. By Claim 2.3, for, each column is 1-shift of K_j, is 2-shift of K_j and is 3-shift = (0-shift) of K_j. Without loss of generality, we can assume and otherwise. We consider two subcases:

Subcase 1.1. For. Then is (n − 2)-shift = (2-shift) of K₁. This implies that . Hence, we need for all. This is a contradiction with. Thus,.

Subcase 1.2. For. Then is (n − 2)-shift = (0-shift) of K₁. This implies that . So, we need for all. Again, we get a contradiction with. Thus,.

Case 2. X₅ = 2 and. Here we have and s_j = 3 otherwise. By the same argument similar to the Case 1, we have K_j is (j − 1)-shift of K₁. Thus, if, then and for is. Also, for position the vertices of K₁, we always have . We consider four Subcases:

Subcase 2.1. d = 1, without loss of generality, we can assume.

For,. Then . The three remaining vertices from each and K_n, most including two values −1, and this is impossible. The same arguments is for.

Subcase 2.2. d = 2, let. Then we have the form.

If n º 1(mod 3), then. This implies that is 0-shift of K₁. Therefore, . Hence, the three columns must be including seven values of −1, two in, three in and two in K_n and this impossible. The same argument is for n º 2(mod 3).

Subcase 2.3. d = 3, let. We have the form. Then for, is 2-shift of K₁. Therefore. Also, . Therefore, two vertices of must has value −1. By symmetry, let. Then by Claim 2.3, there is one case for. Hence, . Therefore, we need two vertices from K_n with value −1. This is a contradiction, (because the vertices of the first column must be a signed dominates by the vertices of the last column). The same argument is for.

Subcase 2.4. d ≥ 4, let (by symmetry is).

We have the form. By Claim 2.3, if then for each two vertices we must have and so for. Since and, then including two vertices with value −1 by 1-shift of two vertices in. Also, including two vertices with value −1 by 1-shift of vertices in and the third ver- tex must be distance 3 from any one has value −1 (Since, Claim 2.3). Thus, the order of the values −1 or 1 of the vertices does not change. Hence the vertices of has the same order of when we have the signed dominating sequence and this impossible is signed dominating sequence of C₉ × C_n for. In Subcases 2.1, 2.2, 2.3 and 2.4 there are many details, we will be omitted it.

Finally, we deduce that does not exist a signed dominating function f of C₉ × C_n for with. Hence,

(20)

From (18) and (20) is. □

Theorem 2.6..

Proof. We define a signed dominating function f as follows:

for and i º j(mod 10), and otherwise. Also, we define

,

,

,

,

,

,

,

,

and otherwise for.

By define f and we have s_j = 4 for all. Notice that: f is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

is a SDF for C₁₀ × C_n when.

For an illustration see Figure 4, (here for, we are changing the functions of the columns:). In all the cases we have.

By Remark 2.2, we have s_j = 0, 2, 4, 6, 8 or 10. Also by Lemma 2.3, if s_j = 0, then and when s_j = 2, is and s_j = 4 is (because if or, then s_j ≥ 6). This implies that

So, we get. □

Corollary 2.7. For, we have

Proof. By Corollary 1.3 we have

(21)

Let us a signed dominating function f as follows: for, , for, , and for,.

By define f, we have s_j = m/3 for. Notice, f is a SDF for C_m × C_n for. Hence,. Then from (21), is for.

For n º 1, 2(mod 3).

Let for. Notice, is a SDF for C_m × C_n for.

Thus,. Hence, by (21) is if. □

3. Conclusions

This paper determined that exact value of the signed domination number of C_m × C_n for m = 8, 9, 10 and arbitrary n. By using same technique methods, our hope eventually lead to determination for general m and n.

Based on the above (Lemma 2.3 and Theorems 1.4, 2.4, 2.5 and 2.6), also by the technique which used in this paper, we again rewritten the following conjecture (This conjecture was mention in [11] ):

Conjecture 3.1.

Cite this paper

RamyShaheen, (2015) On the Signed Domination Number of the Cartesian Product of Two Directed Cycles. Open Journal of Discrete Mathematics,05,54-64. doi: 10.4236/ojdm.2015.53005

References