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

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 Cm × Cn denotes the cartesian product of directed cycles of length m and n. In this paper, we determine the exact values of gs(Cm × Cn) for m = 8, 9, 10 and arbitrary n. Also, we give the exact value of gs(Cm × Cn) when m,  (mod 3) and bounds for otherwise.

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 D1 and D2 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 Cm ´ Cn when m = 3, 4, 5, 6, 7 and arbitrary n. In this paper, we study the Cartesian product of two directed cycles Cm and Cn 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 Cm and Cn for m = 8, 9, 10 and and arbitrary n.

The vertices of a directed cycle Cn 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 Cm ´ Cn, 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 Cm × Cn 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 sj ≥ 0. Furthermore, sj is odd if m is odd and even when m is even.

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

column Kj 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 Cm × Cn with signed dominating sequence. We need the following Lemma:

Lemma 2.3. If then. Furthermore, and.

Proof. Let, then there are of vertices in Kj 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 sj = 2 for j is odd and sj = 4 for j is even. Notice, f is a SDF for C8 × Cn when. Therefore, there is a problem with the vertices of K1 when.

Now, let us define the following functions:

,

,

We note:

f1 is a SDF of C8 × Cn when.

f2 is a SDF of C8 × Cn when.

f3 is a SDF of C8 × Cn when.

f4 is a SDF of C8 × Cn when.

Hence,

(1)

For example, f1 is a SDF of C8 × C12, where, see Figure 1.

{Here, we must note that, for simplicity of drawing the Cartesian products of two directed cycles Cm × Cn, 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 Cm × Cn, 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 C8 × Cn with signed dominating sequence, we have sj = 0, 2, 4, 6 or 8 for. By Lemma 2.3, if sj = 0 then, and if sj = 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 C8 × C12; (b) A corresponding matrix of a signed dominating function of C8 × C12.

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 C8 × Cn 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 C8 × Cn 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 sj = 3 for. Notice, f is a SDF for C9 × Cn for. And f1 is a SDF of C9 × Cn 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 sj = 1, 3, 5, 7 or 9. By Lemma 2.3, if sj = 1 then, sj = 3 then and sj = 5 then (because if, then we need sj ≥ 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 C9 × C6.

If we have one case from the cases X9 ≥ 1, X7 ≥ 2, X5 + X7 ≥ 2 or X5 ≥ 3. Then by (19) is.

Assume the contrary, i.e., (X9 = 0, X7 < 2, X5 + X7 < 2 and X5 < 3).

Hence,. We consider the cases X7 < 2 and X5 < 3, which are including the remained cases, i.e., X7 = 1 and X5 = 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. X7 = 1 and X5 = X9 = 0. Without loss of generality, we can assume sn = 7. Then we have the form. By Claim 2.3, for, each column is 1-shift of Kj, is 2-shift of Kj and is 3-shift = (0-shift) of Kj. 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 K1. 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 K1. This implies that . So, we need for all. Again, we get a contradiction with. Thus,.

Case 2. X5 = 2 and. Here we have and sj = 3 otherwise. By the same argument similar to the Case 1, we have Kj is (j − 1)-shift of K1. Thus, if, then and for is. Also, for position the vertices of K1, 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 Kn, 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 K1. Therefore, . Hence, the three columns must be including seven values of −1, two in, three in and two in Kn 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 K1. 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 Kn 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 C9 × Cn 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 C9 × Cn 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 sj = 4 for all. Notice that: f is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn when.

is a SDF for C10 × Cn 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 sj = 0, 2, 4, 6, 8 or 10. Also by Lemma 2.3, if sj = 0, then and when sj = 2, is and sj = 4 is (because if or, then sj ≥ 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 sj = m/3 for. Notice, f is a SDF for Cm × Cn for. Hence,. Then from (21), is for.

For n º 1, 2(mod 3).

Let for. Notice, is a SDF for Cm × Cn for.

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

Figure 4. A corresponding matrix of a signed dominating function of C10 × C11.

3. Conclusions

This paper determined that exact value of the signed domination number of Cm × Cn 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.

References

[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.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

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