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

Authors: Zehui Shao; Enqiang Zhu; Fangnian Lang
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Denote byγ(G) the domination number of a digraph G and Cm□Cn the Cartesian product of Cm and Cn, the directed cycles of length m,n≥2. In 2010, Liu et al. determined the exact values of γ(Cm□Cn) for m=2,3,4,5,6. In 2013, Mollard determined the exact values of γ(Cm□Cn) for m=3k+2. In this paper, we give lower and upper bounds of γ(Cm□Cn) with m=3k+1 for different cases. In particular, ⌈2k+1n/2⌉≤γ(C3k+1□Cn)≤⌊2k+1n/2⌋+k. Based on the established result, the exact values of γ(Cm□Cn) are determined for m=7 and 10 by the combination of the dynamic algorithm, and an upper bound for γ(C13□Cn) is provided.


---

## Body

## 1. Introduction

All of the digraphs considered in this paper are finite and simple, that is, without multiple edges or loops. For a digraphG=(V,E) and a vertex v∈V, NG+(v) and NG-(v) denote the set of out-neighbors and in-neighbors of v. Given two vertices u and v in G, we say u dominates v if u=v or uv∈E. Let NG+[v]=NG+(v)∪{v}. A vertex v dominates all vertices in NG+[v]. A set D⊆V is a dominating set of G if D dominates V(G). The domination number of G, denoted by γ(G), is the minimum cardinality of a dominating set of G.TheCartesian product of graphs G and H is the graph G□H with the vertex set G×H, and (g,h)(g′,h′)∈E(G□H) if either gg′∈E(G) and h=h′ or hh′∈E(H) and g=g′. The Cartesian product is commutative and associative, having the one-vertex graph as a unit. The subgraph of G□H induced by V(G)×h, where h∈V(H), is isomorphic to G, called a G-layer (over h) and denoted by  Gh. For more information on the Cartesian product of graphs see [1].We use a 0-1 matrix pattern𝒜 with m rows and n columns to represent a dominating set D of Cm□Cn, where (i,j)∈D if and only if the value at the entry (i,j) of 𝒜 equals 1. For example, the pattern in Figure 2 represents the dominating set (the set of black circles) shown in Figure 1. Let P be a pattern; we denote by c(P) the column number of P. Let A and B be patterns; then the pattern AB denotes the concatenation of patterns A and B, and Ak denotes the concatenation of patterns A for k times.Figure 1
A dominating set ofC7□C18.Figure 2
Pattern of the dominating set shown in Figure1.Let[n] denote the set {0,1,…,n-1}. For an integer n≥3, the directed cycle of lengthn is the graph Cn whose vertices are 0,1,…,n-1 and whose edges are the pairs i, i+1, where the arithmetic is done modulo n. We denote V(Cn) by [n]. In this paper, when we consider the Cartesian product graph Cm□Cn of two cycles Cm and Cn, the edge set of Cm is {(i,i+1):i∈[m]} and Cn is {(i+1,i):i∈[n]}. Throughout the paper, when considering the vertex (i,j) in the graph Cm□Cn, we use the arithmetic operations of the index i over modulo m and j modulo n.The dominating set problem requires determining the domination number of a given graph. It has natural applications in numerous facility location problems. In such problems, the vertices of a graph correspond to locations, adjacency represents some notion of accessability, and the goal is to find a subset of locations accessible from all other locations at which to install fire stations, bus stops, post offices, or similar facilities [2]. Dominating sets have also been applied in coding theory [2] and social networks [3]. For more information on the history and applications of the dominating set problem, see [4].In 1990, Faudree and Schelp [5] initially discussed the domination number of the Cartesian product of two undirected graphs. The domination number for Cartesian product of two graphs has attracted lots of attention, and there are many works on undirected graphs (see, e.g., [6–12]). Recently, there are also some works on the domination number of Cartesian product of two directed graphs, in particular, the Cartesian product of directed paths and cycles [13–15].In [13, 15], Liu et al. determined the exact values of γ(Cm□Cn) for m=2,3,4,5,6 and showed the following.Theorem 1.
γ
(
C
m
□
C
n
)
=
m
n
/
3 if m≡0  (mod3) and n≡0  (mod3).Mollard [14] determined exact values of γ(Cm□Cn) for m=3k+2. This paper investigates properties on the domination of Cartesian product of Cm and Cn with m=3k+1. We give lower and upper bounds of γ(Cm□Cn) with m=3k+1 for different cases. In particular, ⌈(2k+1)n/2⌉≤γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+k. Based on the established result, the exact values of γ(Cm□Cn) are determined for m=7 and 10 by the combination of the dynamic algorithm, and an upper bound for γ(C13□Cn) is provided.


## 2. Main Results

### 2.1. Bounds onC3k+1□Cn

Proposition 2 (Mollard [14]).
LetS be a dominating set of Cm□Cn; then for all i∈[n] considered modulo n one has |S∩Cmi-1|+2|S∩Cmi|≥m.Lemma 3.
Letn≥3, k≥1. Then there exists a minimum dominating set D of C3k+1□Cn such that |C3k+1i∩D|≥k for every i∈V(Cn).Proof.
For a dominating setD of C3k+1□Cn, we define a function f as follows:
(1)f(D)=∑t=0n-1‍xt,
where
(2)xt={0,if|D∩C3k+1t|≥k+1,|D∩C3k+1t|,if|D∩C3k+1t|≤k.
We now assume that D is a minimum dominating set of C3k+1□Cn and suppose to the contrary that |C3k+1i+1∩D|<k for some i such that f(D) is maximized. Then there exists a set T={(j,i+1),(j+1,i+1),(j+2,i+1)} such that u∉D for any u∈T. Thus, {(j,i),(j+1,i)}⊆D. By Proposition 2, we have xt=0 if 0<xt+1≤k. Thus D′=D∖{(j+1,i)}∪{(j+1,i+1)} is a dominating set with |D|=|D′| such that f(D′)>f(D), a contradiction with the fact that f(D) is maximized.Lemma 4.
Letn≥3, k≥1. Then there exists a minimum dominating set D of C3k+1□Cn such that |(C3k+1i∪C3k+1i+1)∩D|≥2k+1 for every i∈V(Cn).Proof.
By Lemma3, it is sufficient to consider a minimum dominating set D of C3k+1□Cn such that |C3k+1i∩D|≥k for every i∈V(Cn). If |C3k+1i∩D|=k, together with Proposition 2, we have that |C3k+1i-1∩D|≥k+1, which completes the proof.By Lemmas3 and 4, there is an obvious lower bound in terms of γ(C3k+1□Cn) as follows.Lemma 5.
Letk≥1 and n≥3 be two integers; then
(3)γ(C3k+1□Cn)≥⌈(2k+1)n2⌉.Lemma 6.
For two integersk≥1 and n≥3, then for any ℓ∈[k], one has(1)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+ℓifn≡6ℓ(mod6k+2),(2)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+k-ℓifn≡2+6ℓ(mod6k+2),(3)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kifn≡4+6ℓ(mod6k+2),(4)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+ℓ+1ifn≡3+6ℓ(mod6k+2),(5)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+k-ℓifn≡5+6ℓ(mod6k+2),(6)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kifn≡7+6ℓ(mod6k+2),(7)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kforn≡1(mod6k+2).Proof.
For anyi∈[n], let
(4)Ai={{(3q+i2,i):0≤q≤k},ifniseven,{(3q+2+⌊i2⌋,i):0≤q≤k-1},ifnisodd.
It can be seen that if i≡0(mod2), |Ai|=k+1; otherwise, |Ai|=k. Let S=⋃i=0n-1Ai; then |S|=⌈(2k+1)n/2⌉ and there are at most k vertices, (1,0),(4,0),(7,0),…,(3k-2,0) of C3k+1□Cn of which each is not dominated by S. Denoted by B={(1,n-1),(4,n-1),…,(3k-2,n-1)}, we consider the following cases.
(
1)  n≡6ℓ(mod6k+2).  In this case, it is easy to see that |An-1∩B|=k-ℓ. By adding at most ℓ vertices to S, we get a dominating set of γ(C3k+1□Cn) as required.
(2)  n≡2+6ℓ(mod6k+2).  Since |An-1∩B|=ℓ, we will obtain a desired dominating set of γ(C3k+1□Cn) by adding at most k-ℓ vertices to S.
(3)  n≡4+6ℓ(mod6k+2). Since |An-1∩B|=Ø, we have to add at most k vertices so that a dominating set of γ(C3k+1□Cn) is constructed based on S.
(4)  n≡3+6ℓ(mod6k+2).  Since n-1 is an even and |An-1∩B|=k-ℓ, we have to add at most ℓ vertices to S so that a dominating set of γ(C3k+1□Cn) will be formed.
(5)  n≡5+6ℓ(mod6k+2). Since |An-1∩B|=ℓ, we will obtain a dominating set of γ(C3k+1□Cn) by adding at most k-ℓ vertices to S.
(6)  n≡7+6ℓ(mod6k+2).  Let An-3′={(1+3ℓ+3k,n-3),(2+3ℓ,n-3),(5+3ℓ,n-3),…,(2+3ℓ+3(k-1),n-3)} when 2+3ℓ>2+3ℓ+3k(mod3k+1); otherwise, let An-3′={(1+3ℓ,n-3), (5+3ℓ,n-3),(8+3ℓ,n-3),…,(2+3ℓ+3k,n-3)} when 2+3ℓ<2+3ℓ+3k(mod3k+1); let An-2′=C3k+1n-2∖{(1,n-2),(4,n-2),(7,n-2),…,(3k-2,n-2),(1+3ℓ+3k,n-2)} when 2+3ℓ>2+3ℓ+3k(mod3k+1); otherwise, let An-2′=C3k+1n-2∖{(1,n-2),(4,n-2),(7,n-2),…,(3k-2,n-2),(1+3ℓ,n-2)} when 2+3ℓ<2+3ℓ+3k(mod3k+1); let An-1′={(1,n-1),(4,n-1),…,(3k-2,n-1)}, Ai′=Ai for i∈[n-4]. In this way, if we let D=⋃i=0n-1Ai′, then D is a dominating set of C3k+1□Cn. In addition, |An-3′|=k+1, |An-2′|=2k, and |An-1′|=k. So, D=(((2k+1)n)/2)+((2k-1)/2)=⌊((2k+1)n)/2⌋+k.
(7)  n≡1(mod6k+2).  Let D=∑i=0n-2‍Ai∪{(1+3q,n-1),(3+3q,n-1):0≤q≤k-1}. Then D is a dominating set of C3k+1□Cn with cardinality ⌊(2k+1)n/2⌋+k.The result of Lemmas5 and 6 show the following.Corollary 7.
Letk≥1 and n≥3 be two integers; then
(5)⌈(2k+1)n2⌉≤γ(C3k+1□Cn)≤⌊(2k+1)n2⌋+k.


## 2.1. Bounds onC3k+1□Cn

Proposition 2 (Mollard [14]).
LetS be a dominating set of Cm□Cn; then for all i∈[n] considered modulo n one has |S∩Cmi-1|+2|S∩Cmi|≥m.Lemma 3.
Letn≥3, k≥1. Then there exists a minimum dominating set D of C3k+1□Cn such that |C3k+1i∩D|≥k for every i∈V(Cn).Proof.
For a dominating setD of C3k+1□Cn, we define a function f as follows:
(1)f(D)=∑t=0n-1‍xt,
where
(2)xt={0,if|D∩C3k+1t|≥k+1,|D∩C3k+1t|,if|D∩C3k+1t|≤k.
We now assume that D is a minimum dominating set of C3k+1□Cn and suppose to the contrary that |C3k+1i+1∩D|<k for some i such that f(D) is maximized. Then there exists a set T={(j,i+1),(j+1,i+1),(j+2,i+1)} such that u∉D for any u∈T. Thus, {(j,i),(j+1,i)}⊆D. By Proposition 2, we have xt=0 if 0<xt+1≤k. Thus D′=D∖{(j+1,i)}∪{(j+1,i+1)} is a dominating set with |D|=|D′| such that f(D′)>f(D), a contradiction with the fact that f(D) is maximized.Lemma 4.
Letn≥3, k≥1. Then there exists a minimum dominating set D of C3k+1□Cn such that |(C3k+1i∪C3k+1i+1)∩D|≥2k+1 for every i∈V(Cn).Proof.
By Lemma3, it is sufficient to consider a minimum dominating set D of C3k+1□Cn such that |C3k+1i∩D|≥k for every i∈V(Cn). If |C3k+1i∩D|=k, together with Proposition 2, we have that |C3k+1i-1∩D|≥k+1, which completes the proof.By Lemmas3 and 4, there is an obvious lower bound in terms of γ(C3k+1□Cn) as follows.Lemma 5.
Letk≥1 and n≥3 be two integers; then
(3)γ(C3k+1□Cn)≥⌈(2k+1)n2⌉.Lemma 6.
For two integersk≥1 and n≥3, then for any ℓ∈[k], one has(1)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+ℓifn≡6ℓ(mod6k+2),(2)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+k-ℓifn≡2+6ℓ(mod6k+2),(3)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kifn≡4+6ℓ(mod6k+2),(4)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+ℓ+1ifn≡3+6ℓ(mod6k+2),(5)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+k-ℓifn≡5+6ℓ(mod6k+2),(6)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kifn≡7+6ℓ(mod6k+2),(7)
γ(C3k+1□Cn)≤⌊(2k+1)n/2⌋+kforn≡1(mod6k+2).Proof.
For anyi∈[n], let
(4)Ai={{(3q+i2,i):0≤q≤k},ifniseven,{(3q+2+⌊i2⌋,i):0≤q≤k-1},ifnisodd.
It can be seen that if i≡0(mod2), |Ai|=k+1; otherwise, |Ai|=k. Let S=⋃i=0n-1Ai; then |S|=⌈(2k+1)n/2⌉ and there are at most k vertices, (1,0),(4,0),(7,0),…,(3k-2,0) of C3k+1□Cn of which each is not dominated by S. Denoted by B={(1,n-1),(4,n-1),…,(3k-2,n-1)}, we consider the following cases.
(
1)  n≡6ℓ(mod6k+2).  In this case, it is easy to see that |An-1∩B|=k-ℓ. By adding at most ℓ vertices to S, we get a dominating set of γ(C3k+1□Cn) as required.
(2)  n≡2+6ℓ(mod6k+2).  Since |An-1∩B|=ℓ, we will obtain a desired dominating set of γ(C3k+1□Cn) by adding at most k-ℓ vertices to S.
(3)  n≡4+6ℓ(mod6k+2). Since |An-1∩B|=Ø, we have to add at most k vertices so that a dominating set of γ(C3k+1□Cn) is constructed based on S.
(4)  n≡3+6ℓ(mod6k+2).  Since n-1 is an even and |An-1∩B|=k-ℓ, we have to add at most ℓ vertices to S so that a dominating set of γ(C3k+1□Cn) will be formed.
(5)  n≡5+6ℓ(mod6k+2). Since |An-1∩B|=ℓ, we will obtain a dominating set of γ(C3k+1□Cn) by adding at most k-ℓ vertices to S.
(6)  n≡7+6ℓ(mod6k+2).  Let An-3′={(1+3ℓ+3k,n-3),(2+3ℓ,n-3),(5+3ℓ,n-3),…,(2+3ℓ+3(k-1),n-3)} when 2+3ℓ>2+3ℓ+3k(mod3k+1); otherwise, let An-3′={(1+3ℓ,n-3), (5+3ℓ,n-3),(8+3ℓ,n-3),…,(2+3ℓ+3k,n-3)} when 2+3ℓ<2+3ℓ+3k(mod3k+1); let An-2′=C3k+1n-2∖{(1,n-2),(4,n-2),(7,n-2),…,(3k-2,n-2),(1+3ℓ+3k,n-2)} when 2+3ℓ>2+3ℓ+3k(mod3k+1); otherwise, let An-2′=C3k+1n-2∖{(1,n-2),(4,n-2),(7,n-2),…,(3k-2,n-2),(1+3ℓ,n-2)} when 2+3ℓ<2+3ℓ+3k(mod3k+1); let An-1′={(1,n-1),(4,n-1),…,(3k-2,n-1)}, Ai′=Ai for i∈[n-4]. In this way, if we let D=⋃i=0n-1Ai′, then D is a dominating set of C3k+1□Cn. In addition, |An-3′|=k+1, |An-2′|=2k, and |An-1′|=k. So, D=(((2k+1)n)/2)+((2k-1)/2)=⌊((2k+1)n)/2⌋+k.
(7)  n≡1(mod6k+2).  Let D=∑i=0n-2‍Ai∪{(1+3q,n-1),(3+3q,n-1):0≤q≤k-1}. Then D is a dominating set of C3k+1□Cn with cardinality ⌊(2k+1)n/2⌋+k.The result of Lemmas5 and 6 show the following.Corollary 7.
Letk≥1 and n≥3 be two integers; then
(5)⌈(2k+1)n2⌉≤γ(C3k+1□Cn)≤⌊(2k+1)n2⌋+k.


## 3. On the Domination ofC7□Cn

Lemma 8.
Letk≥1 and n≥3 be two integers. Suppose D is a minimum dominating set of C3k+1□Cn. Let Si=D∩C3k+1i and ai=|Si| for i=0,1,…,n-1. (a)
If there is an integeri such that ai+ai+1=2k+1 (considered modulo n), then one of {ai,ai+1} is k and the other is k+1.(b)
If there is an integeri such that ai=k+1, ai+1=k, ai+2=k+1, and ai+3=k, then for any distinct vertices (j1,i+1), (j2,i+1) in Si+1 and (j3,i+3), (j4,i+3) in Si+3, j1-j2≡0(mod3), j3-j4≡0(mod3); for any distinct vertex (j1′,i), (j2′,i) in Si and (j3′,i+2), (j4′,i+2) in Si+2, |j1′-j2′|≡0(mod3) or |j1′-j2′|=1 and |j3′-j4′|≡0(mod3) or |j3′-j4′|=1, where j1<j2, j3<j4, j1′<j2′, j3′<j4′, and they are taken modulo 3k+1.Proof.
It follows immediately that (a) holds by Lemmas3 and 4. In addition, since ai=k+1,  ai+1=k,  ai+2=k+1,  and ai+3=k, each of vertices of C3k+1i+1 and C3k+1i+3 is dominated by only one vertex; also, only one vertex of C3k+1i+2 is dominated by two vertices. Now we will first show that it is impossible that there are three consecutive vertices in Si. Otherwise, suppose that (s,i), (s+1,i), and (s+2,i) (modulo 3k+1) are three consecutive vertices. We can deduce that vertices (s+1,i+2) and (s+2,i+3) are in Si+2 and Si+3, respectively, so (s+1,i+3) is dominated by both (s+1,i+2) and (s+2,i+3), a contradiction.
Suppose that there are(j1,i+1), (j2,i+1) (or (j3,i+3), (j4,i+3)) in Si+1 (or Si+3) such that j1-j2≢0(mod3) (or j3-j4≢0(mod3)). Then it is easy to show that there exist three consecutive vertices ∈Si or three consecutive vertices (s1,i+2), (s1+1,i+2), and (s1+2,i+2)∈Si+2 (modulo 3k+1), thus (s1,i+1), (s1+1,i+1), and (s1+2,i+1) (modulo 3k+1) can only be dominated by Si, and (s1+4,i+1)∈Si+1 since it is impossible that there are four consecutive vertices in Si+3 by ai+3=k. So, it is an easy task to prove that either (s1+3,i+2) is not dominated by D or (s1+4,i+2) is dominated by two vertices, a contradiction. By using the same approach as above, we also can prove the cases of vertices in Si and Si+2.Lemma 9.
Letk≥1 and n≥3. If D is a minimum dominating set of C3k+1□Cn such that (ai,ai+1,ai+2,ai+3,…,ai+2ℓ)=(k+1,k,k+1,k,…,k+1), where Si=D∩C3k+1i and ai=|Si| for some i, ℓ, then (j,i+1)∈Si+1 if and only if (j+t-1,i+2t-1)∈Si+2t-1 for any j∈{0,1,…,3k} and t∈{1,2,…,ℓ}.Proof.
By Lemma8 and the symmetrical structure of Cm□Cn, we assume without loss of generality  Si+2ℓ-1={(3q,i+2ℓ-1):0≤q≤k-1}. Since each vertex in {(3q-1,i+2ℓ-1):0≤q≤k-1}∪(-2,i+2ℓ-1) is not dominated by C3k+1i+2ℓ-1, we have Si+2ℓ-2={(3q-1,i+2ℓ-2):0≤q≤k-1}∪(-2,i+2ℓ-2). By observing that each vertex in Si+2ℓ-2 needs to be dominated, we have the desired set Si+2ℓ-3. Repeating this process until Si+1 is determined, we have the desired result.Theorem 10.
Letn≥7. Then
(6)γ(C7□Cn)={⌊5n2⌋,n≡0(mod14),⌊5n2⌋+1,n≡3,4,6,8,10,11(mod14),⌊5n2⌋+2,n≡1,2,5,7,9,12,13(mod14).Proof.
Consider the following.
Case
1.  n≡0(mod14).
The lower bound follows from Lemma5, and the upper bound follows from Lemma 6 with ℓ=0 in Case 1.
Case
2.  n≡3,4,6,8,10,11(mod14).
By using Lemmas3 and 4, we obtain that γ(C7□Cn)=⌊5n/2⌋ if and only if n≡0(mod14). Therefore, the desired lower bound is established. Upper bound can be obtained by applying Lemma 6 with k=2 in the following cases:(i)
n≡3(mod14), ℓ=0 in case 4;(ii)
n≡6(mod14), ℓ=1 in case 1;(iii)
n≡8(mod14), ℓ=1 in case 2;(iv)
n≡11(mod14), ℓ=1 in case 5.
We give the upper bound for the casen≡4, 10(mod14) by constructions.
Letn=14k+4. The pattern depicted in Figure 2 is a dominating set of C7□C18 with 46 vertices. Moreover, the leftmost 14 columns induce a dominating set of C7□C14 with 35 vertices. By repeating the leftmost 14 columns for k times, we get a dominating set of C7□C14k+4 with 35k+11 vertices. Therefore, γ(C7□C14k+4)≤35k+11, and thus, γ(C7□Cn)≤⌊5n/2⌋+1.
Letn=14k+10. The pattern depicted in Figure 3 is a dominating set of C7□C24 with 61 vertices. Moreover, the leftmost 14 columns induce a dominating set of C7□C14 with 35 vertices. By repeating the leftmost 14 columns for k times, we get a dominating set of C7□C14k+10 with 35k+26 vertices. Therefore, γ(C7□C14k+10)≤35k+26, and thus, γ(C7□Cn)≤⌊5n/2⌋+1.
Case
3.  n≡1,2,5,7,9,12,13(mod14).
The upper bound follows from Lemma6. We then show the lower bound. Let n≡1(mod14). If there exists a minimum dominating set of C3k+1□Cn with cardinality ⌊5n/2⌋+1, then by Lemmas 3 and 4, we have such a dominating set D with (a0,a1,a2,a3,…,an-2,an-1)=(3,2,3,2,…,2,3), where Si=D∩C7i and ai=|Si|. We without loss of generality assume Sn-2={(0,n-2),(3,n-2)}. Then S1={(1,1),(4,1)} and so S0={(0,0),(3,0),(6,0)}. We now consider Sn-2, Sn-1, and S0 with Sn-2 and S0 known. Then there are four vertices in Sn-1 not dominated by Sn-2∪S0, a contradiction. Therefore, γ(C7□Cn)≥⌊5n/2⌋+2 if n≡1(mod14). By using the same approach, we can obtain the desired lower bound if n≡2,5,7,9,12,13(mod14) and the proof is omitted.Figure 3
A dominating set ofC7□C24.


## 4. On the Domination ofC10□Cn

We use thedynamic algorithm to provide the result on γ(Cm□Cn) for m=10 and 13. We first describe the concept needed to describe our computer checking. The idea is introduced in [16] in a more general framework and extended in [17], but for our purpose the following description will be sufficient.For a graphG and D⊆V(G), we define a function f:V(G)→{0,1} such that f(v)=0 if v∉D and f(v)=1 if v∈D. We call such a function the 2-coloring of G. If for f(v)=0 there exists a vertex u∈NG-(v) such that f(v)=1, then we say v is dominated. We can see that this notation is equivalent to the dominating set and we will use it to describe the dynamic algorithm for this problem.LetC={uiui+1:i∈[n]} be a directed cycle in a weighted digraph G. We say that the sum of the weights of all the edges in C to be the weight of C.Letu be a 2-coloring of Cm□P2; u is said to be an (a,b)-vertex if the number of ones in the first copy ofCmequals a and the second equals b (see, e.g., the left side of the vertex in Figure 4 is a (3,2)-vertex). An (a,b)-vertex is said to be redundant if it is dominated and any removal of one vertex in the first column destroys the domination.Figure 4
Two vertices ofD7.LetT={(ai,bi):1≤i≤t}. We define a weighted digraph DmT (when no confusion can arise, the set T is omitted and the digraph is denoted by Dm) as follows.The vertices ofDmT consist of all the nonredundant 2-colorings of Cm□P2. Let u=u1u2 be a vertex of DmT. Then u1 and u2 represent the 2-colorings of Cm□P2 restricted to the first and second copies of Cm. Let u and v be two vertices of DmT. Then uv~ denotes the 2-coloring of Cm□P3 obtained by applying u2 and v1 to the consecutive copies of Cm. For each vertex u of DmT, we make an arc from u to v in DmT if and only if the following conditions are fulfilled:(i)
u2 equals v1,(ii)
each of the vertices ofCm1∪Cm2 is dominated (by Cm0∪Cm1),(iii)
for each(a,b)-vertex of DmT, (a,b)∈T.Finally, the weight ofuv is the number of ones in Cm1 of v.LetT={(2,3),(3,2)}. Figure 4 shows two vertices of D7T. We can see that the 2-coloring (0010010) of the second copy of C7 of the first vertex equals the first copy of C7 of the second vertex. Moreover, the weight of the second copy of C7 of the first vertex is 2. It follows that A(D7T) has an arc from the first (left) vertex to the second (right) with weight 2.Lemma 11.
Letm,n≥3. Then Dm possesses a directed cycle of length n with weight k if and only if Cm□Cn contains a minimal dominating set S with |S|=k.Proof.
IfS is a minimal dominating set of Cm□Cn, then S restricted to Cmi∪Cmi+1 is a 2-coloring 𝒞 of Cm□P2. Since S is minimal, we have that 𝒞 is nonredundant.
IfDm possesses a directed cycle of length n, we concatenate the second cycle Cm of each vertex of the cycle and then obtain a dominating set S of Cm□Cn. Since each vertex in the cycle is nonredundant, we have that S is minimal.We define a weighted adjacency matrixA(Dm) of Dm as follows. Let V(Dm)={v1,v2,…,vK}. Then
(7)A(Dm)i,j={w(vivj),vivj∈Dm,+∞,vivj∉Dm,
where w(vivj) is the weight of the edge vivj.LetA=(a)p×q (p rows, q columns) and B=(b)q×r (q rows, r columns) be two weighted adjacency matrices. We define A multiplied by B as follows
(8)(a1,1a1,2⋯a1,qa2,1a2,2⋯a2,p⋮⋮⋮⋮ap,1ap,2⋯ap,q)×(b1,1b1,2⋯b1,rb2,1b2,2⋯b2,r⋮⋮⋮⋮bq,1bq,2⋯bq,r)=(c1,1c1,2⋯c1,rc2,1c2,2⋯c2,r⋮⋮⋮⋮cp,1cp,2⋯cp,r),
where cs,t=min1≤i≤q{as,i+bi,t} for s∈{1,2,…,p} and t∈{1,2,…,r}.We denote byAn the nth power of A; we have the following result.Theorem 12.
Letm,n≥3 and A(Dm) be the weighted adjacency matrix of Dm with K vertices. Then one has
(9)γ(Cm□Cn)=min{((A(Dm))n)i,i:1≤i≤K}.Lemma 13.
Letn≥10, γ(C10□Cn)≤⌊7n/2⌋+2, and D a dominating set with cardinality ⌊7n/2⌋+2. (a)
Ifn is odd, then |D∩(C10i∪C10i+1)|≤8 for any i∈V(Cn).(b)
Ifn is even, then |D∩(C10i∪C10i+1)|≤9 for any i∈V(Cn) but at most one integer i0 such that |D∩(C10i0∪C10i0+1)|=9.Proof.
(a) Suppose that there existsi0∈[n-1] such that |D∩(C10i0∪C10i0+1)|≥9. We can deduce that
(10)|D∩⋃j∈[n-1],j∉{i0,i0+1}‍V(C10j)|≤72(n-2)-12.
Thus, by the pigeonhole principle it can be seen that there exist some i∈[n-1] such that |D∩(C10i∪C10i+1)|<7, which contradicts with Lemma 4.
(b) The proof is similar to (a).Theorem 14.
Letn≥10. Then
(11)γ(C10□Cn)={⌊7n2⌋,n≡0(mod20),⌊7n2⌋+1,n≡3,6,14,17(mod20),⌊7n2⌋+2,n≡4,7,8,9,10,11,12,13,16(mod20),⌊7n2⌋+3,n≡1,2,5,15,18,19(mod20).Proof.
Whenn≡0,3,6,14,17  (mod20), the result follows from Lemmas 6, 8, and 9. Otherwise, let T={(3,4),(4,3),(3,5),(5,3),(4,4)}. We implemented the algorithm as described above, and the digraph D10T was created and it has 4905 vertices. By Lemma 13, it can be seen that there may exist at most one (x,y)-vertex such that x+y=9 in the auxiliary graph D10. We consider each possible auxiliary graph D10, whose vertex set is the union of that of D10T and one (x,y)-vertex with x+y=9. Note that D10 has only 4906 vertices; the matrix multiplication can be done easily. By using matrix multiplication, we found a formula as stated in Theorem 14. (Such parameters a and b exist; see [17].) If γ(C10□Cn) (for some n) is greater than ⌊7n/2⌋+2, then γ(C10□Cn)=⌊7n/2⌋+3.Remark 15.
Note that when Lemmas4 and 13 are applied, we can operate matrix multiplication on the graph D10T1 whose row number is 4906. It can be clearly seen that |D∩(C10i∪C10i+1)|≤9 for any i∈V(Cn) with the condition of Lemma 13, and it is natural to consider the graph D10T2, where T2=T∪{(3,6),(4,5),(5,4),(6,3)}. However, D10T2 has 24845 vertices, whose vertex number is much more than that of D10. Therefore, Lemmas 4 and 13 play the key role in computing the exact values of γ(C10□Cn), and this helps to make many hard instances become easy to solve.


## 5. Bounds on the Domination Number ofC13□Cn

We will conclude this work with upper bounds for the domination number ofC13□Cn.Theorem 16.
Letn≥13. Then
(12)γ(C13□Cn)≤{⌊9n2⌋,n≡0(mod26),⌊9n2⌋+1,n≡3,6,20,23(mod26),⌊9n2⌋+2,n≡9,10,12,14,16,17(mod26),⌊9n2⌋+3,n≡4,7,8,11,13,15,18,19,22(mod26),⌊9n2⌋+4,n≡1,2,5,21,24,25(mod26).Proof.
We show the desired weight for all cases in Table1, where r≡n(mod26) and (c,ℓ) stands for case (c) with ℓ in Lemma 6. For example, the result of the case n≡0(mod26) follows from case 1 with ℓ=0 in Lemma 6.
Also, patternsA–Gwith 13 rows are presented (see Figures 5 and 6). By repeating the pattern of A for k times and concatenating H∈{B,C,D,E,F,G}, we will obtain a pattern AkH of C13□Cn, where n=26k+c(H). From the above, it can be seen that all the desired upper bounds are established.Table 1
Constructions for upper bounds ofC13□Cn.
r
0
1
2
3
4
5
6
7
8
(
c
,
ℓ
)
(
1,0
)
(
7,0
)
(
2,0
)
(
4,0
)
A
k
B
(
5,0
)
(
1,1
)
A
k
C
(
2,1
)
r
9
10
11
12
13
14
15
16
17
(
c
,
ℓ
)
(
4,1
)
A
k
D
(
5,1
)
(
1,2
)
(
6,1
)
(
2,2
)
(
4,2
)
A
k
E
(
5,2
)
r
18
19
20
21
22
23
24
25
(
c
,
ℓ
)
(
1,3
)
A
k
F
(
2,3
)
(
4,3
)
A
k
G
(
5,3
)
(
1,4
)
(
6,3
)Figure 5
A
B: dominating set of C13□C30; AC: dominating set of C13□C33; AD: dominating set of C13□C36.Figure 6
A
E: dominating set of C13□C42; AF: dominating set of C13□C45; AG: dominating set of C13□C48.



---

*Source: 619695-2013-12-19.xml*