# The Domination Complexity and Related Extremal Values of Large 3D Torus

Authors: Zehui Shao; Jin Xu; S. M. Sheikholeslami; Shaohui Wang
Journal: Complexity
 (2018)

---

## Abstract

Domination is a structural complexity of chemical molecular graphs. A dominating set in a (molecular) graphG=V,E is a subset S⊆V such that each vertex in V\S is adjacent to at least one vertex in S. The domination number γG of a graph G is the minimum size of a dominating set in G. In this paper, computer-aided approaches for obtaining bounds for domination number on torus graphs are here considered, and many new exact values and bounds are obtained.


---

## Body

## 1. Introduction

The structure of molecular graphs is a broad area among chemistry, biology, and mathematics. In particular, domination number or dominating complexity has attracted considerable attention in the general case [1–7], like coding theory and combinatorial design. Due to a variety of applications, it has been studied on various types of graphs such as generalized Petersen graphs [8–11], hypercubes [12, 13], Fibonacci cubes [14], Kneser graphs [15–18], torus graphs [19–21], and grid graphs [22, 23]. Others are referred to [24–26].In this work, we consider certain graphs without loops or multiple edges. A dominating set in a graphG=V,E is a subset S⊆V such that each vertex in V\S is adjacent to at least one vertex in S. The domination number γG of a graph G is the minimum cardinality of a dominating set in G. A dominating set of a graph G is a γG set if it has cardinality γG. A dominating set S is an independent dominating set, if no two vertices in S are adjacent. The independent domination number iG of a graph G is the minimum cardinality of an independent dominating set in G. For S⊆VG, the cardinality of a minimum dominating set of G containing S is denoted by γG∣S, that is,
(1)γGS=minT:TisadominatingsetofGandS⊆T.For two graphsG and H, the Cartesian product G□H is a graph with vertex set VG×VH and two vertices (u1,v1) and (u2,v2) are adjacent if and only if either u1=u2 and v1v2∈EH or v1=v2 and u1u2∈EG. The gird Gj,k is Pj□Pk, the cylinder Cj,k for j≥3 is Cj□Pk, the torus Tj,k for j≥3 and k≥3 is Cj□Ck, and the 3D torus Tm,n,k for given m, n, k≥3 is Cm□Cn□Ck. The subgraph of G□H induced by VG×v is isomorphic to G. It is called a G-fiber and is denoted by Gv.The domination number has attracted considerable attention in the general case [1, 2]. Due to a variety of applications, it has been studied on various types of graphs such as generalized Petersen graphs [8–11], hypercubes [12, 13], Fibonacci cubes [14], Kneser graphs [15, 16, 18], torus graphs [19–21], and grid graphs [22, 23]. Others are referred to [24–26].Dominating sets in some special graphs have applied in coding theory and combinatorial design. For instance, there is a natural relation between dominating sets of torus graphs and covering codes in the Lee metric [21], and dominating sets in a type of Kneser graphs are also related to Steiner system [18].The following result is a special case of Theorem 3.3 in [19]:Theorem 1.
γC5ℓ1□C5ℓ2=5ℓ1ℓ2foranyℓ1,ℓ2≥1.LetAutG be the automorphism group of graph G. We say two subsets S1⊆VG and S2⊆VG are equivalent if there exists a mapping g∈AutG such that S1=gS2. For a subset S⊆VG, the orbit of S is the family SAutG=gS∣g∈AutG.


## 2. The Approaches

### 2.1. ILP-Based Search

LetG be a graph and S be a dominating set of G. We use a Boolean variable xv to denote if a vertex v is in S, that is, xv=1 if v∈S.The following is the well-known integer linear programming model for finding a minimum dominating set ofG:ILPDominatingSet(2)min∑v∈VGxv,(3)subjectto∑u∈Nvxu≥1foranyv∈VG,(4)xv∈0,1foranyv∈VG.


### 2.2. Extending Dominating Sets from Inequivalent Seeds

Sometimes, we can succeed to obtain the independent domination numberiG of a graph G in a reasonable time but it fails to exhaustively search the domination number γG. In such cases, based on Observation 1, we can obtain iG first to assume there are two adjacent vertices in a minimum dominating set.Observation 1.
LetG be a graph. If there is a minimum dominating set S such that ∣S∣<iG, then S contains two adjacent vertices.Observation 2.
LetG be a graph and S be a family of inequivalent subsets of VG. If there is a minimum dominating set S of G containing a subset isomorphic to one element in S, then γG=minγG∣S∣S∈S.Based on the above observations, we first select a familyS of inequivalent subsets of the vertex set of a considered graph G then extend each subset S∈S to a minimum dominating set, that is, we compute γG∣S. We apply the following procedure to compute the domination number of G (using a 2.66 GHz Intel Core (TM) i7-5600U CPU).Procedure 1
Procedure MinDomination(G, S);
Input: a graph G and a family S of inequivalent subsets of VG.
begin
minDom ←+∞;
for all S∈S do
computeγG∣S by solving the model ILPDominatingSet with additional
constraints thatxv=1 for each v∈S;
if (γG∣S<minDom) then minDom←γG∣S;
endfor
Solve the modelILPDominatingSet with additional constraints
that∑v∈Txv≤T−1 for each T in the orbit of a set S∈S and
letγ′ be the objective value;
return min{minDOM, γ′};
end.


### 2.3. Numerical Results

In this section, we determine the domination number of five torus.Theorem 2.
γC21□C21=95.Proof.
The upper bound follows from the dominating set depicted in Figure1.
Next, we show thatγC21□C21≥95. Consider a family of inequivalent subset Ss1,s2,…,s8 where
(5)s1=1,1,1,4,4,1,4,4,s2=1,1,1,4,4,1,3,4,s3=1,1,1,4,4,1,5,4,s4=1,1,1,4,3,1,3,4,s5=1,1,1,4,3,1,5,4,s6=1,1,1,4,3,1,4,3,s7=1,1,1,4,3,1,4,5,s8=1,1,1,4,5,1,5,4.
We run ProcedureMinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥95 for each S∈S. The results are presented in Table 1.
Moreover, we obtain thatγ′≥95 in only 2774 seconds by running MinDomination. From the above computational results, we have γC21□C21≥95.Theorem 3.
γC22□C22=104.Proof.
The upper bound follows from the dominating set depicted in Figure2.
From the computational results above, we haveγC22□C22≥104.Theorem 4.
γC23□C23=114.Proof.
The upper bound follows from the dominating set depicted in Figure3.
Next, we show thatγC23□C23≥114. First, it takes 12520 seconds to obtain iC23□C23=115 using Gurobi optimizer. Since γC23□C23≤114<iC23□C23=115, we deduce that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the following inequivalent family S=W1,W2,…,W8, where
(6)W1=1,3,2,0,3,2,0,0,0,1,W2=1,3,2,0,2,2,0,0,0,1,W3=1,3,2,0,4,2,0,0,0,1,W4=1,3,2,0,3,1,0,0,0,1,W5=1,3,2,0,3,3,0,0,0,1,W6=1,3,1,0,3,2,0,0,0,1,W7=1,3,1,0,2,2,0,0,0,1,W8=1,3,1,0,4,2,0,0,0,1.
We run ProcedureMinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥114 for each S∈S, and the results are presented in Table 2.
Moreover, we obtain thatγ′≥114 in 16753 seconds by running MinDomination. From the above computational results, we have γC23□C23≥114.Theorem 5.
γC24□C24=120.Proof.
The upper bound follows from the dominating set depicted in Figure4.
Next, we show thatγC24□C24≥120. Suppose, to the contrary, that γC24□C24≤119.
First, it takes 18974 seconds to obtainiC24□C24=120 using Gurobi optimizer. By assumption, γC24□C24≤119<iC24□C24=120. By Observation 1, we conclude that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the inequivalent family S=W1,W2,…,W8 defined in the proof of Theorem 4. We run Procedure MinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥120 for each S∈S, and the results are presented in Table 3.
Moreover, we obtain thatγ′≥120 in 23764 seconds by running MinDomination. From the above computational results, we have γC24□C24≥120, contradicting with the initial assumption that γC24□C24≤119. Thus, γC24□C24=120.Theorem 6.
γC26□C26=144.Proof.
The upper bound follows from the dominating set depicted in Figure5.
Next, we show thatγC26□C26≥144. Suppose, to the contrary, that γC26□C26≤143.
First, it takes 938743 seconds to obtainiC26□C26=144 using Gurobi optimizer. By assumption, γC26□C26≤143<iC26□C26=144. By Observation 1, we conclude that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the inequivalent family S=W1,W2,…,W8 defined in the proof of Theorem 4. We run Procedure MinDomination to extend each S∈S for a minimum dominating set with a time limit 200000 seconds. Although we failed to determine the exact values of γG∣S within 200000 seconds, we are able to confirm that γG∣S≥144 for each S∈S. This suffices to confirm the lower bound 144, and the results are presented in Table 4.
Moreover, we obtain thatγ′≥144 in 465326 seconds by running MinDomination. From the above computational results, we have γC26□C26≥144, contradicting with the initial assumption that γC26□C26≤143. Thus, γC26□C26=144.Figure 1
A dominating set with 95 vertices inC21□C21.Table 1
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
s1
96
1805
s2
95
2542
s3
95
1918
s4
95
1365
s5
95
1032
s6
95
1273
s7
95
3892
s8
96
1640Figure 2
A dominating set with 104 vertices inC22□C22.Figure 3
A dominating set with 114 vertices inC23□C23.Table 2
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
115
10535
W2
115
12360
W3
115
15515
W4
115
11740
W5
115
16170
W6
115
23005
W7
115
18650
W8
114
1325Figure 4
A dominating set with 120 vertices inC24□C24.Table 3
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
121
40
W2
122
135
W3
122
206
W4
122
75
W5
122
17
W6
122
110
W7
122
685
W8
122
90Figure 5
A dominating set with 144 vertices inC26□C26.Table 4
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
144
120245
W2
≥144
171506
W3
≥144
187364
W4
≥144
189346
W5
≥144
196393
W6
≥144
193245
W7
≥144
179873
W8
≥144
162785By Theorem1, we have that if n≡0 (mod 5), then γCn□Cn=n2/5. Inspired by the result in [21] and the above computational results, the following conjecture is proposed.Conjecture 1.
Letn≥4. Then, we have
(i)
if n≡1 (mod 5), then γCn□Cn=n2+2n−8/5,
(ii)
if n≡4 (mod 5), then γCn□Cn=n2+n/5.


## 2.1. ILP-Based Search

LetG be a graph and S be a dominating set of G. We use a Boolean variable xv to denote if a vertex v is in S, that is, xv=1 if v∈S.The following is the well-known integer linear programming model for finding a minimum dominating set ofG:ILPDominatingSet(2)min∑v∈VGxv,(3)subjectto∑u∈Nvxu≥1foranyv∈VG,(4)xv∈0,1foranyv∈VG.


## 2.2. Extending Dominating Sets from Inequivalent Seeds

Sometimes, we can succeed to obtain the independent domination numberiG of a graph G in a reasonable time but it fails to exhaustively search the domination number γG. In such cases, based on Observation 1, we can obtain iG first to assume there are two adjacent vertices in a minimum dominating set.Observation 1.
LetG be a graph. If there is a minimum dominating set S such that ∣S∣<iG, then S contains two adjacent vertices.Observation 2.
LetG be a graph and S be a family of inequivalent subsets of VG. If there is a minimum dominating set S of G containing a subset isomorphic to one element in S, then γG=minγG∣S∣S∈S.Based on the above observations, we first select a familyS of inequivalent subsets of the vertex set of a considered graph G then extend each subset S∈S to a minimum dominating set, that is, we compute γG∣S. We apply the following procedure to compute the domination number of G (using a 2.66 GHz Intel Core (TM) i7-5600U CPU).Procedure 1
Procedure MinDomination(G, S);
Input: a graph G and a family S of inequivalent subsets of VG.
begin
minDom ←+∞;
for all S∈S do
computeγG∣S by solving the model ILPDominatingSet with additional
constraints thatxv=1 for each v∈S;
if (γG∣S<minDom) then minDom←γG∣S;
endfor
Solve the modelILPDominatingSet with additional constraints
that∑v∈Txv≤T−1 for each T in the orbit of a set S∈S and
letγ′ be the objective value;
return min{minDOM, γ′};
end.


## 2.3. Numerical Results

In this section, we determine the domination number of five torus.Theorem 2.
γC21□C21=95.Proof.
The upper bound follows from the dominating set depicted in Figure1.
Next, we show thatγC21□C21≥95. Consider a family of inequivalent subset Ss1,s2,…,s8 where
(5)s1=1,1,1,4,4,1,4,4,s2=1,1,1,4,4,1,3,4,s3=1,1,1,4,4,1,5,4,s4=1,1,1,4,3,1,3,4,s5=1,1,1,4,3,1,5,4,s6=1,1,1,4,3,1,4,3,s7=1,1,1,4,3,1,4,5,s8=1,1,1,4,5,1,5,4.
We run ProcedureMinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥95 for each S∈S. The results are presented in Table 1.
Moreover, we obtain thatγ′≥95 in only 2774 seconds by running MinDomination. From the above computational results, we have γC21□C21≥95.Theorem 3.
γC22□C22=104.Proof.
The upper bound follows from the dominating set depicted in Figure2.
From the computational results above, we haveγC22□C22≥104.Theorem 4.
γC23□C23=114.Proof.
The upper bound follows from the dominating set depicted in Figure3.
Next, we show thatγC23□C23≥114. First, it takes 12520 seconds to obtain iC23□C23=115 using Gurobi optimizer. Since γC23□C23≤114<iC23□C23=115, we deduce that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the following inequivalent family S=W1,W2,…,W8, where
(6)W1=1,3,2,0,3,2,0,0,0,1,W2=1,3,2,0,2,2,0,0,0,1,W3=1,3,2,0,4,2,0,0,0,1,W4=1,3,2,0,3,1,0,0,0,1,W5=1,3,2,0,3,3,0,0,0,1,W6=1,3,1,0,3,2,0,0,0,1,W7=1,3,1,0,2,2,0,0,0,1,W8=1,3,1,0,4,2,0,0,0,1.
We run ProcedureMinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥114 for each S∈S, and the results are presented in Table 2.
Moreover, we obtain thatγ′≥114 in 16753 seconds by running MinDomination. From the above computational results, we have γC23□C23≥114.Theorem 5.
γC24□C24=120.Proof.
The upper bound follows from the dominating set depicted in Figure4.
Next, we show thatγC24□C24≥120. Suppose, to the contrary, that γC24□C24≤119.
First, it takes 18974 seconds to obtainiC24□C24=120 using Gurobi optimizer. By assumption, γC24□C24≤119<iC24□C24=120. By Observation 1, we conclude that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the inequivalent family S=W1,W2,…,W8 defined in the proof of Theorem 4. We run Procedure MinDomination to extend each S∈S for a minimum dominating set and determine γG∣S for each S∈S. It can be seen that γG∣S≥120 for each S∈S, and the results are presented in Table 3.
Moreover, we obtain thatγ′≥120 in 23764 seconds by running MinDomination. From the above computational results, we have γC24□C24≥120, contradicting with the initial assumption that γC24□C24≤119. Thus, γC24□C24=120.Theorem 6.
γC26□C26=144.Proof.
The upper bound follows from the dominating set depicted in Figure5.
Next, we show thatγC26□C26≥144. Suppose, to the contrary, that γC26□C26≤143.
First, it takes 938743 seconds to obtainiC26□C26=144 using Gurobi optimizer. By assumption, γC26□C26≤143<iC26□C26=144. By Observation 1, we conclude that any minimum dominating set has two adjacent vertices. Now, we may assume w.l.o.g. that 0,0,0,1 are in a minimum dominating set. We consider the inequivalent family S=W1,W2,…,W8 defined in the proof of Theorem 4. We run Procedure MinDomination to extend each S∈S for a minimum dominating set with a time limit 200000 seconds. Although we failed to determine the exact values of γG∣S within 200000 seconds, we are able to confirm that γG∣S≥144 for each S∈S. This suffices to confirm the lower bound 144, and the results are presented in Table 4.
Moreover, we obtain thatγ′≥144 in 465326 seconds by running MinDomination. From the above computational results, we have γC26□C26≥144, contradicting with the initial assumption that γC26□C26≤143. Thus, γC26□C26=144.Figure 1
A dominating set with 95 vertices inC21□C21.Table 1
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
s1
96
1805
s2
95
2542
s3
95
1918
s4
95
1365
s5
95
1032
s6
95
1273
s7
95
3892
s8
96
1640Figure 2
A dominating set with 104 vertices inC22□C22.Figure 3
A dominating set with 114 vertices inC23□C23.Table 2
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
115
10535
W2
115
12360
W3
115
15515
W4
115
11740
W5
115
16170
W6
115
23005
W7
115
18650
W8
114
1325Figure 4
A dominating set with 120 vertices inC24□C24.Table 3
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
121
40
W2
122
135
W3
122
206
W4
122
75
W5
122
17
W6
122
110
W7
122
685
W8
122
90Figure 5
A dominating set with 144 vertices inC26□C26.Table 4
The results for extending seeds fromS.
Seed (S)
γG∣S
Time (s)
Seed (S)
γG∣S
Time (s)
W1
144
120245
W2
≥144
171506
W3
≥144
187364
W4
≥144
189346
W5
≥144
196393
W6
≥144
193245
W7
≥144
179873
W8
≥144
162785By Theorem1, we have that if n≡0 (mod 5), then γCn□Cn=n2/5. Inspired by the result in [21] and the above computational results, the following conjecture is proposed.Conjecture 1.
Letn≥4. Then, we have
(i)
if n≡1 (mod 5), then γCn□Cn=n2+2n−8/5,
(ii)
if n≡4 (mod 5), then γCn□Cn=n2+n/5.


## 3. Results and Discussions: Domination Number of 3D Torus

In this section, we determine the domination number of some 3D torusTm,n,k, where m, n, k≥3. Denote the vertices in Sm,ni by vi,jk for 0≤i≤m−1 and 0≤j≤n−1. For any γTm,n,k set S, let Sm,ni=S∩Cm□Cni fori=1,…,k.Theorem 7.
Fork≥3, γT3,3,k≥3k/2.Proof.
It is easy to verify thatγT3,3,k≥3k/2 for k=3,4,5. Let k≥6 and S be a γT3,3,k set such that S3,3i:S∩S3,3i≥5and1≤i≤k is as small as possible. First, we show that S3,3i≠0 for each i. Suppose, to the contrary, that S3,3i=0 for some i, say i=3. To dominate the vertices of S3,33, we must have S3,32+S3,34≥9. Clearly, the set
(7)S′=S−S3,32∪S3,34∪v0,01,v2,21,v1,11,v0,23,v2,03,v1,14,v0,05,v2,25is a dominating set of T3,3,k of size less than ∣S∣ which is a contradiction. Thus, S3,3i≥1 for each i.
Next, we show that ifS∩S3,3i=S∩S3,3i+1=1 for some i, then S∩S3,3i−1≥3 and S∩S3,3i+2≥3. Let S∩S3,3i=S∩S3,3i+1=1 for some i, say i=2. Assume without loss of generality that v1,12∈S. If v1,13∈S, then to dominate the vertices v0,0j,v2,2j,v0,2j,v2,0j for j=2,3, we must have v0,0j,v2,2j,v0,2j,v2,0j∣j=14⊆S and so S∩S3,3j≥4 for j=1,4.
Ifv1,23∈S (the cases v1,03∈S, v0,13∈S, and v2,13∈S are similar), then to dominate the vertices v0,02,v2,22,v0,22,v2,02,v0,03,v0,13,v1,03,v2,03,v2.13, we must have S∩S3,31≥4 and S∩S3,34≥5. If v0,03∈S (the cases v0,23∈S, v2,03∈S, and v2,23∈S are similar), then to dominate the vertices v0,22,v2,02,v2,22,v1,23,v2,13,v2,23, we must have S∩S3,3j≥3 for j=1,4.
Letwi=S∩S3,3i for each i and define f on 1,…,k by
(8)fiwi,ifwi,1≥2orwi−1=1andwi=2,wi−1,ifwi,1=1andwi≥3,wi+1,ifwi=wi−1=1.
Clearly,∑i=1kfi=S and fi+fi+1≥3 for each i. It follows that
(9)2γT3,3,k=2S=2∑i=1kfi=∑i=1kfi+fi+1≥3k,yielding γT3,3,k≥3k/2. Since γT3,3,k is integer, we obtain the desired bound.Theorem 8.
Letk≥3 be an integer. Then
(i)
γT3,3,k=3k/2 if k=6 or k≡0,1,3 (mod 4),
(ii)
γT3,3,k≤3k/2+1 if k≡2 (mod 4) and k≠6.Proof.
LetG=T3,3,k and
(10)A=v1,14ℓ+1,v0,04ℓ+2,v2,24ℓ+2,v1,14ℓ+3,v0,24ℓ+4,v2,04ℓ+40≤ℓ≤k4−1.
(i)
Ifk≡0 (mod 4), then A is a dominating set of G of size 3k/2, if k≡1 (mod 4), then A∪v0,2k,v2,0k is a dominating set of G with cardinality 2k, and if k≡3 (mod 4), then A∪v0,0k−2,v2,2k−2,v1,1k−1,v0,2k,v2,0k is a dominating set of G of size 3k+1/2.
Ifk=6, then set v0,01,v1,01,v2,12,v0,23,v1,23,v2,04,v0,05,v1,15,v2,26 is a dominating set of G with cardinality 9. Therefore, we have γG≤3k/2 when k=6 or k≡0,1,3 (mod 4).
(ii)
Ifk≡2 (mod 4), then the set A∪v0,0k−1,v1,1k−1,v1,1k,v2,2k is a dominating set of G with cardinality 3k/2+1. Therefore, we have γG≤3k/2+1 if k=4p+2 for p≥2.Remark 1.
We have succeed to compute all the exact values ofγT3,3,k for k≤34 and γC3□C3□Ck=3k/2+1 only if k∈10,14,22,26,34.Theorem 9.
Fork≥3, γT3,4,k=2k.Proof.
LetG=T3,4,k. First, we show that γG≤2k. Let
(11)A=v0,33ℓ+1,v1,13ℓ+1,v2,03ℓ+2,v2,23ℓ+2,v0,13ℓ+3,v1,33ℓ+30≤ℓ≤k3−1.
Ifk≡0 (mod 3), then A is a dominating set of G with cardinality 2k. If k≡1 (mod 3), then A∪v2,0k,v2,2k is a dominating set of G with cardinality 2k. If k≡2 (mod 3), then A∪v2,0k−1,v2,2k−1,v0,3k,v1,1k is a dominating set of G with cardinality 2k. Therefore, we have γG≤2k.
Now, we show thatγG≥2k. It is not hard to see that γG≥2k for k=3,4. Assume k≥5 and let S be a γG set. Denote the vertices in S3,4i by vi,jk for 0≤i≤2 and 0≤j≤3. First, we show that S3,4i≠0 for each i. Suppose, to the contrary, that S3,4i=1 for some i, say i=3. To dominate the vertices of S3,43, we have S3,42+S3,44>12. Clearly, the set
(12)S′=S−S3,42∪S3,44∪v0,31,v1,11,v2,02,v2,22,v0,13,v1,33,v2,04,v2,24,v0,35,v1,15is a dominating set of G of size less than ∣S∣ which is a contradiction. Thus, S3,4i≥1 for each i. Next, we show that there is no i such that S3,4i+S3,4i+1≤3. Suppose, to the contrary, that S3,4i+S3,4i,1≤3 for some i, say i=1. We may assume without a loss of generality that S3,41≤2 and S3,42=1 and that v0,32∈S. To dominate the vertices of S3,42, we must have S∩S3,43≥5. Now, the set
(13)S′=S−S3,43∪v1,12,v2,03,v2,23,v0,13,v1,33is a γG set contradicting the choice of S. Hence, S3,4i+S3,4i+1≥4 for each i. Thus,
(14)γG=2S=2∑i=1kS∩S3,4i=∑i−1kS∩S3,4i+S∩S3,4i+1≥4k,and this completes the proof.Applying analogous approaches described in Section2, we can obtain substantial results on domination of multidimensional torus. The exact values of some 3D torus Tm,n,k are presented in Table 5. Let
(15)Tnk=Cn□Cn□,…,□Cm⏟ktimes.Note that when n=3, the domination of Tnk corresponds to the classic ternary covering codes of length k. By the results of [27], it is clear that γT33=5, γT34=9, and γT35=27. Using the above approaches, we obtained some new bounds and exact values of γTnk. The results are presented in Table 6.Table 5
Exact values of some 3D torusTm,n,k.
m,n\k
3
4
5
6
7
8
9
10
(3,3)
5
6
8
9
11
12
14
16
(3,4)
8
10
12
14
16
18
20
(3,5)
13
15
18
20
23
25
(3,6)
18
21
24
27
30
(3,7)
25
28
32
35
(3,8)
32
36
40
(3,9)
41
45
(4,4)
12
15
16
20
23
24
29
(4,5)
18
20
25
28
30
36
(4,6)
24
28
32
36
40
(4,7)
34
38
42
48
(5,5)
20
26
31
34
38
40
(5,6)
30
35
40
45
50Table 6
Bounds and exact values ofγTnk.
n,k
(21,2)
(22,2)
(23,2)
(24,2)
(25,2)
(26,2)
(27,2)
γTnk
95
104
114
120
125
144
152–155
n,k
(3,3)
(4,3)
(5,3)
(6,3)
(7,3)
γTnk
5
12
20
36
49
n,k
(3,4)
(4,4)
(5,4)
γTnk
9
32
73–85
(n, k)
(3,5)
(4,5)
γTnk
27
100–141Moreover, some dominating sets corresponding to upper bounds are also listed below. Inspired by the computational results, the following conjecture is proposed.Conjecture 2.
(i)
For 3<n≤k, γC3□Cn□Ck=nk/2,
(ii)
For n, k≥3, γC6□Cn□Ck=nk.
(16)γC4□C4□C4≤12:Aγ−set:v0,01,v0,23,v0,24,v1,01,v1,02,v1,23,v2,14,v2,21,v2,34,v3,03,v3,12,v3,32.γC5□C5□C5≤20:Aγ−set:v0,01,v0,04,v0,24,v0,32,v1,12,v1,15,v1,35,v1,43,v2,04,v2,21,v2,23,v2,41,v3,02,v3,15,v3,32,v3,34,v4,13,v4,21,v4,43,v4,45.γC6□C6□C6≤36:Aγ−set:v0,01,v0,04,v0,21,v0,24,v0,41,v0,44,v1,13,v1,16,v1,32,v1,35,v1,52,v1,55,v2,01,v2,04,v2,22,v2,25,v2,43,v2,46,v3,12,v3,15,v3,31,v3,34,v3,53,v3,56,v4,01,v4,04,v4,23,v4,26,v4,42,v4,45,v5,12,v5,15,v5,33,v5,36,v5,53,v5,56.γC7□C7□C7≤49:Aγ−set:v0,01,v0,14,v0,27,v0,33,v0,46,v0,52,v0,65,v1,06,v1,12,v1,25,v1,31,v1,44,v1,57,v1,63,v2,04,v2,17,v2,23,v2,36,v2,42,v2,55,v2,61,v3,02,v3,15,v3,21,v3,34,v3,47,v3,53,v3,66,v4,07,v4,13,v4,26,v4,32,v4,45,v4,51,v4,64,v5,05,v5,11,v5,24,v5,37,v5,43,v5,56,v5,62,v6,03,v6,16,v6,22,v6,35,v6,41,v6,54,v6,67.γC4□C4□C4□C4≤32:Aγ−set:0,0,0,0,0,0,3,2,0,1,1,2,0,1,2,0,0,2,0,1,0,2,3,3,0,3,1,3,0,3,2,1,1,0,1,1,1,0,2,3,1,1,0,3,1,1,3,1,1,2,1,0,1,2,2,2,1,3,0,2,1,3,3,0,2,0,0,3,2,0,2,0,2,1,1,1,2,1,3,2,2,2,1,3,2,2,3,0,2,3,0,1,2,3,2,2,3,0,1,2,3,0,3,1,3,1,0,0,3,1,2,3,3,2,0,2,3,2,2,1,3,3,1,0,3,3,3,3.γC4□C4□C4□C4□C4≤141:Aγ−set:0,0,0,0,0,0,0,0,0,1,0,0,0,3,1,0,0,1,3,3,0,0,2,2,1,0,0,2,2,2,0,0,3,0,3,0,0,3,1,3,0,1,0,2,0,0,1,0,3,2,0,1,1,1,0,0,1,1,1,3,0,1,2,0,2,0,1,2,3,0,0,1,3,1,1,0,2,0,1,2,0,2,0,2,0,0,2,1,0,1,0,2,1,0,3,0,2,1,2,2,0,2,2,1,2,0,2,2,2,0,0,2,3,0,0,0,2,3,2,3,0,2,3,3,1,0,3,0,1,3,0,3,0,3,3,0,3,1,1,1,0,3,1,2,0,0,3,2,0,0,0,3,2,3,2,0,3,3,1,1,0,3,3,2,3,1,0,0,1,3,1,0,0,2,2,1,0,0,3,0,1,0,1,1,3,1,0,2,0,1,1,0,2,1,0,1,0,2,2,0,1,0,2,3,2,1,0,3,3,0,1,1,0,1,1,1,1,1,0,3,1,1,1,2,1,1,1,1,3,1,1,1,2,0,0,1,1,2,1,2,1,1,3,0,2,1,1,3,1,1,1,1,3,2,3,1,2,0,0,3,1,2,0,3,1,1,2,1,1,0,1,2,1,2,3,1,2,1,3,3,1,2,2,1,2,1,2,2,2,2,1,2,2,3,3,1,2,3,3,1,1,3,0,2,1,1,3,0,2,2,1,3,1,0,0,1,3,1,0,2,1,3,2,0,0,1,3,3,1,3,1,3,3,2,1,1,3,3,3,1,1,3,3,3,2,2,0,0,0,2,2,0,0,2,1,2,0,1,1,1,2,0,1,2,0,2,0,2,0,3,2,0,2,2,1,2,0,3,0,3,2,0,3,1,2,2,1,0,0,0,2,1,0,3,3,2,1,1,2,0,2,1,1,2,2,2,1,2,0,2,2,1,2,3,0,2,1,3,0,1,2,1,3,1,3,2,1,3,3,1,2,2,0,1,2,2,2,0,3,3,2,2,1,0,1,2,2,1,1,3,2,2,2,0,1,2,2,2,2,1,2,2,3,1,0,2,2,3,2,0,2,2,3,2,2,2,3,0,0,1,2,3,0,1,0,2,3,1,0,2,2,3,1,3,1,2,3,1,3,2,2,3,2,1,1,2,3,2,2,3,2,3,3,0,3,2,3,3,2,3,3,0,0,1,2,3,0,0,2,3,3,0,1,0,0,3,0,1,0,2,3,0,1,1,2,3,0,1,3,3,3,0,2,0,1,3,0,3,1,0,3,0,3,2,0,3,0,3,3,2,3,1,0,0,0,3,1,0,0,3,3,1,1,3,1,3,1,2,1,0,3,1,2,1,1,3,1,2,2,3,3,1,3,2,2,3,1,3,3,3,3,2,0,0,2,3,2,0,1,1,3,2,0,2,1,3,2,1,1,3,3,2,1,3,0,3,2,2,0,3,3,2,2,3,2,3,2,3,0,2,3,2,3,2,3,3,3,0,0,2,3,3,0,3,0,3,3,1,1,3,3,3,1,2,1,3,3,1,3,1,3,3,2,1,3,3,3,2,3,0,3,3,3,0,2,3,3,3,2,2,3,3,3,3,0.



---

*Source: 3041426-2018-07-02.xml*