On Domination Number of Mixed-Grid Graph Volume 2 - Issue 3

Ramy Shaheen*

• Department of Mathematics Faculty of Science, Tishreen University, Syria

Received: February 03, 2020;   Published: February 27, 2020

*Corresponding author: Ramy Shaheen, Department of Mathematics Faculty of Science, Tishreen University, Lattakia, Syria

DOI: 10.32474/CTBB.2020.02.000137

Abstract PDF

Abstract

A mixed graph GM (V, E, A) is a graph containing unoriented edges (set E) as well as oriented edges (set A), referred to as arcs. In this paper we calculate the domination number of the Cartesian product of a path Pm with directed path Pn (mixed-grid graph p_m × p_n) for some values of m and arbitrary n.

Keywords: graph, directed graph, Cartesian product, path, directed path, mixed graph, mixed-grid graph, dominating set, domination number.

Introduction

All graphs and digraphs are assumed to be loop less and without duplicate edges or arcs. A mixed graph GM (V, E, A) is a graph containing unoriented edges (set E) as well as oriented edges (set A), referred to as arcs. This notion was first introduced in [1]. Let G = (V₁,E) be a graph and D = (V₂, A) be a digraph. The Cartesian product G × D is the mixed-graph with vertex set V (G × D) = V1(G) ×V2 (D) and edge (arc) set is ((u₁, v₁), (u₂,v₂ )∈ E(G × D) if and only if either v₁ = v₂ and (u1,u2 )∈ E(G) or u₁ = u₂ and( v₁,v₂ )∈ A(D). A subset S of the vertex set V (G × D) is a dominating set of (G × D) if for each vertex V ∈G × D there exists a vertex u ∈ s such that (u, v) is an edge (arc) of G × D . The domination number of G × D , γ G × D , is the cardinality of the smallest dominating set of G × D . Let Pm be a path with vertex set V (P_m) = {1, 2,..., n} , and edge set E(P_m) = {(i, i +1) :1 ≤ i ≤ n −1} and let Pn be a directed path with vertex set V (P_n ) = {1,2,...,n}, and arc set A(P_n ) = {(i, i +1) :1 ≤ i ≤ n −1}. Then for Cartesian product P_m and P_n is mixed-grid graph P_m × P_n with V (P_m × P_n ) = {(i, j) :1 ≤ i ≤ m,1 ≤ j ≤ n}, such that there is an arc from (i, j) to ( p, q)if and only fi = p and q − j = 1and is an edge from (i, j) to ( p, q)if and only if j = q and p − i = 1. The i’^th row of V (P_m × P_n ) is R_i = {is a directed pathPn(i, j): j=1,2,...,n} The j’^th column K_j = {(i, j):is a path P_m(i, j):i=1,2,...,m} . If S is a dominating set for P_m × P_n, then we denote W_j = S ∩ K _j.

Let S_j= |W_j| , where the sequence (s1, s2, .....,sn ) is called a dominating sequence corresponding to S. For 1 ≤ i ≤ n , the vertices of j-column are dominated by vertices of j-column or (j-1) column. The vertices of the first column are dominated only by [2] vertices of K1. Also, for 1 ≤ i ≤m, the vertices of i-row are dominated by vertices of i-row or (i −1) − row. The vertices of the first row are dominated only by vertices of R1 or R2. Thus, the following is true γ (P_m× P_n) ≤ γ ( P_m× P_n ) ≤ γ ( P_n × P_n ). For finding domination number of grid graphs P_m × P_n, Jacobson and Kinch in [2], were calculated the domination number of cartesian product of undirected paths P_m and P_n for m = 1, 2, 3, 4 . The cases m = 5, 6 were calculated by Chang and Clark [3]. Also, Chang et al. [4], established the upper bounds of cartesian product of undirected paths Pm and Pn for 5 ≤ m ≤ 10 and arbitrary n. In [5], Gravier and Mollard given un upper and lower bounds of general cartesian product of two undirected paths. Goncalves et al. [6] proved Chang’s conjecture saying that for every 16 ≤ n ≤ m,γ (P_m × P_n ) = [(n +1)(m + 2) / 5] − 4. For domination number of directed grid graphs, Liu et al. [7], they studied the domination number of P_m × P_n for m = 2, 3, 4, 5, 6 and arbitrary n. Also, in [8] the author studied the domination number of P_m × P_n for arbitraries m and n.

Main Results

In this section we calculate the domination number of the Cartesian product of a path P_m and a directed path P_n for some values of m and arbitrary n.

Observation

Since for each vertex (i, j)∈V (P_m × Pn ) has two undirected degrees in V(K_j) one outdegree in V(K_j+1) + and one indegree from V(K_j-1), then can it dominates at must four vertices of P_m × Pn with itself. Thus, implies that γ (P_m × Pn ) ≥ mn / 4.

Observation

Let S be a dominating set of P_m × P_n. Since the vertices of the first column are dominated only by vertices of K₁. Also, for 1 ≤ i ≤ n , the vertices of j-column are dominated by vertices of j-column or (j-1)-column. Then the following are holds:

1. s₁ ≥ [m / 3].
2. s_{j/ + 3sj+1≥m for allj=1,....,n
3 s j−1 + 4sj + sj+1 ≥ 2mfor all j = 2,....,n}

Lemma

There is a minimum dominating set S for P_m × P_n with dominating sequence ( s₁,s₂,....,s_n) such that, for all j =1, 2,..., n, , is [( 2) / 4] [ / 2] j m+ ≤ s ≤ m .

Proof: Let S be a minimum dominating set for P_m × P_n with dominating sequence (s₁,s₂,....,s_n ). Assume that for some j, s_j is large. Then we modify S by moving some vertices from column j to column j +1, such that the resulting set is still dominating set for P_m × P_n (because each vertex in s ∩ K_jis dominates only vertices from K_j and K_j+1 ). For 1 ≤ i ≤ m and 1 ≤ i ≤ n , let W = s∩{(i, j), (i +1, j), (i + 2, j), (i + 3, j)}. If W ≥ 3 , then we have three cases.

Case: If {(i, j), (2, j)} ⊆ S or {(m −1, j(m, j)} ⊆ S . Then we can moving (1, j) to (1, j +1) or (m, j) to (m, j +1) . Furthermore, S is still dominating set of P_m × P_n.

Case: |W| = 4 , then we put

S₁ = S −W ∪ i j i + j + i + j + i + j

Case: W = 3 then we have two sub cases

a. SubCase: W = 3 and W = S ∩{(i, j),(i +1, j),(i + 2, j),(i + 3, j)}={(i, j), (i+1, j), (i+2, j)} or W = {(i+1, j), (i+2, j), (i+3, j)} . Two cases are similar by symmetry, for the first we put S₁=(S −W) ∪{(i, j), (i + 2, j), (i +1, j +1)} and for the second we put S₁=(S −W) ∪{(i, j), (i + 3, j), (i + 2, j +1)}

b. Subcase: |W| = 3 and W = S ∩{(i, j),(i +1, j),(i + 2, j),(i + 3, j)}= {(i, j), (i+1, j), (i+3, j)} or W = {(i, j), (i + 2, j), (i+3, j)}. Also, two cases are similar by symmetry. Then we change S, respectively as follows: S₁=(S −W) ∪{(i, j),(i+3, j)(i+1,j+1)} , S₁=(S −W) ∪{(i, j), (i+3, j),(i+2, j+1)} , see (Figure 1) for cases 2, 3. We repeat this process if necessary eventually leads to a dominating set with required properties. Also, we get S₁ is a dominating set for P_m × P_n with |S| = |S1|. Thus, we can assume that every four consecutive vertices of the j’^th column include at most two vertices of S. This implies that S_j ≤ [m / 2], for all 1 ≤ j ≤ n .To prove the lower bound, we suppose that K_j ∩ D is be a maximum, i.e S_j = [m / 2] Then there at must m −[m / 2] vertices in K_j+1 are not dominated (Figure 2). By maximality of S_j, does not have three successive vertices do not belong to S (i.e., does not exist three successive vertices K_j+1 from does not dominated by vertices from S ∩ K_j ). Thus, implies that S_j+1 ≥ (m −[m / 2]) / 2 = [(m + 2) / 4] By

c. Lemma: always we have a minimum dominating set S with dominating sequence 1 2 ( s₁,s₂,...., s_n ), such that [(m + 2) / 4] ≤ S_j ≤ [m / 2], for all j = 1, 2,..., n

Proposition: Clearly,γ(P₁ × P_n)= γ(P_n)= [n/2]

Theorem γ(P₂ × P_n ) = n

Proof. Let S be a set defined as follows We have |S| = n , also S is a dominating set of P₂ × P_n. By Observation 2, we have S_j + 3S_j+1 ≥ m. Which implies that, if S_j = 0 is S_j+1 = 2 and if S_j = 1 is S_j+1 ≥ 1. Then we get γ(P₂ × P_n ) = Σ_j=1ⁿs_j ≥n Thusγ (γ(P₂ × P_n) = n

Theorem: γ(P₃ × P_n ) = n

Proof: We define S as follows: S = {(2, j) :1 ≤ j ≤ n}
Certainly, S is a dominating set of P₃ × P_n with |S| = n Also, we have γ (P₃ × P_n ) ≥ γ (P₂ × P_n ) = n Thus

γ(P₄ × P_n )=n

Proposition: γ(P₄ × P_n≤[3n/2] )

Proof. Here, we define S as follows:

s={(1, 4j- 3), (4, 4j-3 3) : 1 ≤j ≤ [n/ 2]} ∪{(3, 4j- 2) :1≤j≤ [n/2] }

Certainly S is a dominating set P₄ × P_n (see Figure 3 for γ(P₄ × P₁₀ ), . Also, we have

|S| = 2[n /4]+ 2[(n −1) / 4] + [(n − 2) / 4] + [(n − 3) / 4] = [3n / 2]

γ (P₄ × P_n) ≤ [3n / 2].

Proposition:

a. There only two cases of (S_j,S_j+1) = (1,1) such that K_j∩S = {(1,j )} and K_j+1 ∩ S = {(3,_j+1)} or K_j ∩ S = {(4, j)} and K_j+1 ∩ S = {(2, j +1)} Furthermore, two cases are similar by symmetry. We consider the first case.

b. The case (S_j, S_j+1 S_j+2) = (1,1,1) is not possible.
c. The case (S₁, S₂, S₃) = (2,1,1) is not possible.
d. If K₂ ∩ S = {(1, 2) then S₁ = 3
e. If K₃ ∩ S = {(1, 3)} then S₁ + S₂ = 4 .

Proof: Immediately by drawing.

Proposition: If (S_j , S_j+1) = (1,1) , then (S_j−2, S_j−3) = (2, 2) or (S_j−2r , S_j−2r+1) = (1, 2) {where 1 ≤ r and 1 ≤ j − 2r . Furthermore, the second case repeated until exist two columns before K_j , K_j+1, contains four vertices from S.

Proof: From Proposition 4.5.1 (1), we have K_j ∩ S = {(1, j)} and K_j+ ∩ S = {(3, j +1)}. This implies that K_j−1 ∩ S = {(3, j −1), (4, j −1)} and then {(1, j − 2)} ⊆ K_j−2 ∩ S . If |K_j−2 ∩S| = 2 then S_j−1 + S_j−2 = 4 otherwise | K_j−2 ∩ S| = 1 and K_j-3 ∩ = {(3,j- 3), (4,j-4)} {(1, 4)} 4 K_j-4∩ S={(1,j-4)} and repetition this case until (S₁, S₂) = (1, 2) or (S₂, S₃) = (1, 2) {where j is odd or even, respectively}.

Theorem: γ(P₄ × P_n=[3n/2]

Proof. By Lemma 2.1, 1 ≤ S_j ≤ 2 for all j = 1,..., n .We have two cases:

Case 1. S_j + S_j+1 ≥ 3 for j = 1, …, n-1. Then we get

Case 2. S_j + S_j+1 = 2 for some 1 ≤ j ≤ n −1 . Thus, we have (S_j + S_j+1) = (1,1). By Proposition 2.3(1), we consider the first case K_j ∩ S = {(1,j)} and K_j+1 ∩ S = {(3,j+ 1)} . There are two subcases

Sub Case S_j−2r + S_j−2r+1 = 4 {where 4 ≤ j ≤ −2r ≤ j − 2 }. Then we can assume that each two columns including at least three

vertices from S and then

Sub Case (S_j−2, S_j−1) = (S_j−4, S_j−3) = ... = (S_j−2r + S_j−2r+1) = (1, 2) .
Then we study the cases:

a. If j − 2r = 1 i.e., S₁= 1 and this impossible.
b. If j − 2r = 2 . Then K2 ∩ S = {(1, 3)} and {(3,1), (4, 2)} ⊆ K₂ ∩ S . But, needs (1,1)∈ S or (2,1)∈ S for dominate (1, 1). Furthermore S₁ + S₂ = 4 .

c. If j − 2r = 3. Then K₃ ∩S = {(1,3)} and {(3, 2), (4, 2)} ⊆ K₂ ∩ S . Then needs (1,1)∈ S and (3,1)∈ S or (4,1)∈ S , also S₁ + S₂ = 4 .

Now, we conclude that for all cases, when exist the case (S_j , S_j+1) = (1,1) there is the case S_j−2r + S_j−2r+1 ≥ 4 before repeated the case (S_q , S_q+1) = (1,1) . Thus, we can assume that each four columns including at least 6 vertices from S. Finally, get γ (P₄ × P_n)= Finally, Proposition 2.2 together with the last result gets

γ (P₄ × P_n) ≤ [3n/2]

γ (P₅ × P_n) ≤ [3n / 2]+1.

Proof: Let S defined as follows:

S{(1,1), (3,1), (5,1)}∪ {(3, 2j ) :1 ≤j ≤ [n/2]} ∪{(1, 2j+ 1):(5, 2j+ 1) :1 [(n- 1) / 2]}

We can check that S is a dominating set of P₅ × P_n (see Figure 3 for γ (P₅ × P₁₂ )), with

S = 3 + [n / 2] + 2[(n −1) / 2] = [3n / 2] +1We need to the following fact:

Fact 1.

1. There is one possible for (S_j , S_j+1, S_j+2 ) = (1, 2,1) . Furthermore, if (S_j , S_j+1, S_j+2 ) = (1, 2,1) then K_j ∩ S = {(3, j)}, K_j+1 ∩ S = {(1, j+1),(5 + j +1)} and K_j ∩ S = {(3, j + 2)} .

2. (S₁, S₂, S₃) = (2, 2,1) in not possible.
3. (S₁, S₂, S₃)= (2,1, 2) in not possible. Furthermore, S₁+ S₂ ≥ 4 and S₁+ S₂ + S₃ ≥ 6

Proof. 1). By Observation 2.2, we have (S_j , S_j+1) = (1,1) is not possible. But, (S_j , S_j+1) = (1, 2) or (2, 1) are possible, also (S_j , S_j+1, S_j+2 ) = (1, 2,1) is possible. Thus for S_j+2 = 1 we must have {(1, 1), (2, 1)} K_j+1 ∩ S = j + j + , {(4, j +1), (5, j +1)} or {(1, j +1), (5, j +1)}. For the first and second needs S_j = 2 , we rejected. Then for the case {(1, 1), (5, 1)} K_j+1 ∩ S = j + j + , we get S_j = 1 and S_j+2= 1 , furthermore K_j ∩ S = {(3, j)}and K_j ∩ S = {(3, j + 2)} .

2). From (1), if S₃ = 1 then we have K₂ ∩ S = {(1, 2), (2, 2)},{(4, 2), (5, 2)}or {(1, 2), (5, 2)} . For all these cases S₁ = 2 is not possible.
3) Immediately from prove (1).

Now, From Lemma 2.1, we have 1 ≤ S_j ≤ 3 . Also, Observation 2.2, gets (3, 1, 1) is not possible. By Fact 1, we include that S₁ + S₂ + S₃ ≥ 6 , furthermore if S_j = 2 then for r ≥ 2. Thus

By recent results with (1), we get the required.

Theorem γ(P₆ × P_n=n

Proof. Let S defined as follows: S = S = {(2,1), (5, j) :1≤ j ≤ n} . Definitely S is a dominating set of P₆ × P_n with γ (P₆ × P_n ) ≤ |S| = 2n.

By Observation 2.2, S₁ ≥ 2 and (S_j , S_j+1) = (1, 2) is not possible. This implies that γ(P₆ × P_n)= Thus we get

Theorem γ(P₇ × P_n)=2n+2

Proof. For P₇ × P_n we define S as follows:

S = {(1,1),(3,1),(5,1),(7,1),}∪{(3,2 j),(7,2 j) :1≤ j ≤ |n / 2| }∪{(1,2 j +1),(5,2 j +1) :1≤ j ≤ |(n −1) / 2| }

We have S is a dominating set of P₇ × P_n (see (Figure 4), for γ(P₇ × P₁₅ ), with |s| = 4 + 2|n / 2| + 2| (n −1) / 2| = 2n + 2 We need to the following fact.

a. Fact 2.
b. s₁ ≥ 3
c. s₁ ≥ 3
d. (s₁,s₂ ) = (4,1) and (s₁,s₂,s₃)= (3, 2, 2)
e. s₁+s₂ ≥ 6 or s₂+s₃ ≥ 6

Proof. 1). It is clear from Observation 2.2.

2) Immediately by drawing.
3) From (2), it’s clear.
4) By Observation 2.2, we have s_j 3s_j+1 ≥ m. This implies that (s_j, S_j+1) = (3,1) is not possible. Then we get the required for (4).
Now, by Fact 2, We conclude that

Thus, by (2) together with the last result gets (P₇ × P_n ) = 2n +2.

References

1. Sotskov YN,Tanaev VS (1976) Chromatic polynomial of a mixed graph.VestsiAkademieNavuk BSSR, SeriyaFiz. Mat Navuk Russianpp. 620-623.
2. Chang T, Clark W (1993) The domination number of the 5×n and 6×n grid graphs. J of Graph Theory 17(1): 81-107.
3. Chang T,Clark W, Hare E (1994) Domination number of complete grid graphs. I Ars Combinatoria38:97-111.
4. Gravier S, Modlard M (1997) On domination number of Cartesian product of paths complete. Discrete applied mathematics 80: 2497-2550.
5. Goncalves D, Pinlou A, Rao M, Thomasse S (2011)The Domination Number of Grids.SIAM J Discrete Math25(3): 1443-
6. Liu J, Zhang X,Chen x, Meng j (2011) On domination Number of Cartesian Product of directed paths. JCombinatorial Optimization22(4): 651-662.
7. Shaheen R (2012)On the domination number of Cartesian products of two directed paths. Int J ContempMath Sciences 7(36): 1785-1790.
8. Jacobson M, Kinch L (1983) On the domination number of products of graphs.Ars Combinatoria 18: 33-44.