On the Signed Domination Number of the Cartesian Product of Two Directed Cycles ()

Ramy Shaheen^{*}

Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

**DOI: **10.4236/ojdm.2015.53005
PDF
HTML XML
4,218
Downloads
5,583
Views
Citations

Department of Mathematics, Faculty of Science, Tishreen University, Lattakia, Syria.

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}* ×

Keywords

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

Share and Cite:

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

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_{1} and D_{2} 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_{8} × C_{n} when. Therefore, there is a problem with the vertices of K_{1} when.

Now, let us define the following functions:

,

,

We note:

f_{1} is a SDF of C_{8} × C_{n} when.

f_{2} is a SDF of C_{8} × C_{n} when.

f_{3} is a SDF of C_{8} × C_{n} when.

f_{4} is a SDF of C_{8} × C_{n} when.

Hence,

(1)

For example, f_{1} is a SDF of C_{8} × C_{12}, 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_{8} × 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.

(a) (b)

Figure 1. (a) A signed dominating function of C_{8} × C_{12}; (b) A corresponding matrix of a signed dominating function of C_{8} × C_{12}.

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_{8} × 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. □

Figure 2. The form.

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_{8} × 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_{9} × C_{n} for. And f_{1} is a SDF of C_{9} × 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

Figure 3. A corresponding matrix of a signed dominating function of C_{9} × C_{6}.

If we have one case from the cases X_{9} ≥ 1, X_{7} ≥ 2, X_{5} + X_{7} ≥ 2 or X_{5} ≥ 3. Then by (19) is.

Assume the contrary, i.e., (X_{9} = 0, X_{7} < 2, X_{5} + X_{7} < 2 and X_{5} < 3).

Hence,. We consider the cases X_{7} < 2 and X_{5} < 3, which are including the remained cases, i.e., X_{7} = 1 and X_{5} = 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_{7} = 1 and X_{5} = X_{9} = 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_{1}. 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_{1}. This implies that . So, we need for all. Again, we get a contradiction with. Thus,.

Case 2. X_{5} = 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_{1}. Thus, if, then and for is. Also, for position the vertices of K_{1}, 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_{1}. 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_{1}. 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_{9} × 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_{9} × 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_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × C_{n} when.

is a SDF for C_{10} × 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. □

Figure 4. A corresponding matrix of a signed dominating function of C_{10} × C_{11}.

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.

Conflicts of Interest

The authors declare no conflicts of interest.

[1] |
Haas, R. and Wexler, T.B. (1999) Bounds on the Signed Domination Number of a Graph. Discrete Mathematics, 195, 295-298. http://dx.doi.org/10.1016/S0012-365X(98)00189-7 |

[2] | West, D.B. (2000) Introduction to Graph Theory. Prentice Hall, Inc., Upper Saddle River. |

[3] | Dunbar, J.E., Hedetniemi, S.T., Henning, M.A. and Slater, P.J. (1995) Signed Domination in Graphs, Graph Theory, Combinatorics and Application. John Wiley & Sons, Inc., Hoboken, 311-322. |

[4] | Cockayne, E.J. and Mynhart, C.M. (1996) On a Generalization of Signed Domination Functions of Graphs. Ars Combinatoria, 43, 235-245. |

[5] |
Hattingh, J.H. and Ungerer, E. (1998) The Signed and Minus k-Subdomination Numbers of Comets. Discrete Mathematics, 183, 141-152. http://dx.doi.org/10.1016/S0012-365X(97)00051-4 |

[6] |
Xu, B. (2001) On Signed Edge Domination Numbers of Graphs. Discrete Mathematics, 239, 179-189. http://dx.doi.org/10.1016/S0012-365X(01)00044-9 |

[7] |
Broere, I., Hattingh, J.H., Henning, M.A. and McRae, A.A. (1995) Majority Domination in Graphs. Discrete Mathematics, 138, 125-135. http://dx.doi.org/10.1016/0012-365X(94)00194-N |

[8] |
Zelinka, B. (2005) Signed Domination Numbers of Directed Graphs. Czechoslovak Mathematical Journal, 55, 479-482. http://dx.doi.org/10.1007/s10587-005-0038-5 |

[9] |
Karami, H., Sheikholeslami, S.M. and Khodkar, A. (2009) Lower Bounds on the Signed Domination Numbers of Directed Graphs. Discrete Mathematics, 309, 2567-2570. http://dx.doi.org/10.1016/j.disc.2008.04.001 |

[10] |
Atapour, M., Sheikholeslami, S., Hajypory, R. and Volkmann, L. (2010) The Signed k-Domination Number of Directed Graphs. Central European Journal of Mathematics, 8, 1048-1057. http://dx.doi.org/10.2478/s11533-010-0077-5 |

[11] | Shaheen, R. and Salim, H. (2015) The Signed Domination Number of Cartesian Products of Directed Cycles. Submitted to Utilitas Mathematica. |

Journals Menu

Contact us

+1 323-425-8868 | |

customer@scirp.org | |

+86 18163351462(WhatsApp) | |

1655362766 | |

Paper Publishing WeChat |

Copyright © 2023 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.