# Bounds on the Size of the Minimum Dominating Sets of Some Cylindrical Grid Graphs

Authors: Mrinal Nandi; Subrata Parui; Avishek Adhikari
Journal: International Journal of Combinatorics
 (2014)

---

## Abstract

Letγ
P
m
□
C
n denote the domination number of the cylindrical grid graph formed by the Cartesian product of the graphs P
m, the path of length m, m
≥
2, and the graph C
n, the cycle of length n, n
≥
3. In this paper we propose methods to find the domination numbers of graphs of the form P
m
□
C
n with n
≥
3 and m
=
5 and propose tight bounds on domination numbers of the graphs P
6
□
C
n, n
≥
3. Moreover, we provide rough bounds on domination numbers of the graphs P
m
□
C
n, n
≥
3 and m
≥
7. We also point out how domination numbers and minimum dominating sets are useful for wireless sensor networks.


---

## Body

## 1. Introduction

The problem of domination is one of the most widely studied topics in graph theory: the 1998 book by Haynes et al. [1] contains a bibliography with over 1200 papers on the subject. The domination problem was studied from the 1950s onwards, but the rate of research on domination significantly increased in the mid-1970s.The signed domination number of a graphG was defined in [2] and has been studied by several authors including [2, 3]. Independent dominating sets were introduced into the theory of games by Morgenstern in [4]. For an extensive survey of domination problems and comprehensive bibliography the readers are referred to [5]. The study of domination numbers of products of graphs was initiated by Vizing [6]. He conjectured that the domination number of the Cartesian product of two graphs is always greater than or equal to the product of the domination numbers of the two factors, a conjecture which is still unproven. In [7], a link is shown between the existence of tilings in Manhattan metric with {
1
}, bowls and minimum total dominating sets of Cartesian products of paths and cycles. Domination numbers of Cartesian products were intensively investigated in [7–9].The graphs considered here are finite, nonempty, connected, undirected without loops and without multiple edges. Besides these, any undefined terms in this paper may be found in Harary [10].LetG be a simple graph whose vertex set and edge set are V
(
G
) and E
(
G
), respectively. The set D
⊆
V
(
G
) of a simple graph G is called a dominating set if every vertex v
∈
V
(
G
)
∖
D is adjacent to some vertex u
∈
D. The domination number of the graph G is the cardinality of a smallest dominating set of the graph G; it is usually denoted by γ
(
G
) and dominating set with smallest cardinality is called a minimum dominating set of the graph G.For any two graphsG and H, the Cartesian product G
□
H is the graph with vertex set V
(
G
)
×
V
(
H
) and with edge set E
(
G
×
H
) such that (
u
1
,
v
1
)
(
u
2
,
v
2
)
∈
E
(
G
×
H
), whenever v
1
=
v
2 and u
1
u
2
∈
E
(
G
), or u
1
=
u
2 and v
1
v
2
∈
E
(
H
) [11].In this paper we follow the following notations and terminologies. The numbers0,1
,
2
,
…
,
n
-
1 always denote the vertices of a path P
n or a cycle C
n. Let γ
(
P
m
□
P
n
) and γ
(
P
m
□
C
n
) denote the domination numbers of Cartesian product graphs P
m
□
P
n and P
m
□
C
n, respectively. Let (
G
)
v
=
G
×
{
v
}, where v
∈
V
(
H
) and (
H
)
u
=
{
u
}
×
H, where u
∈
V
(
G
). (
G
)
v and (
H
)
u are called the layers of G and H, respectively. Moreover, layer of a dominating set means D
∩
(
P
m
)
i for i
∈
V
(
C
n
). Next we shall define the term modified concatenation of two dominating sets of P
m
□
C
n
1 and P
m
□
C
n
2. If D
1 and D
2 are two dominating sets of P
m
□
C
n
1 and P
m
□
C
n
2, respectively, then the modified concatenation of D
1 and D
2 is a subset D of P
m
□
C
n
1
+
n
2 such that D
∩
(
P
m
)
i
=
D
1
∩
(
P
m
)
i, i
=
0,1
,
…
,
n
1
-
1, and D
∩
(
P
m
)
n
1
+
i
=
D
2
∩
(
P
m
)
i, i
=
0,1
,
…
,
n
2
-
1; that is, the ith (
P
m
)-layer of D is coming from the ith (
P
m
)-layer of D
1 if 0
≤
i
≤
n
1
-
1 and from the ith (
P
m
)-layer of D
2 if n
1
≤
i
≤
n
1
+
n
2
-
1. The illustration of modified concatenation is shown in Figure 1.Figure 1
Modified concatenation of dominating sets ofP
5
□
C
6 and P
5
□
C
3 to get dominating set for P
5
□
C
9.One of the most challenging problems concerning the domination number of Cartesian products of graphs is the proof of the Vizing Conjecture, namely,γ
(
G
□
H
)
≥
γ
(
G
)
γ
(
H
) [6]. Despite numerous results showing its validity in some special cases, till date the conjecture remains an open problem. Partial works have been made towards finding the domination numbers of some particular Cartesian products. This problem also seems to be difficult one and the authors of [12] proved that even for subgraphs of P
m
□
P
n, this problem is NP-complete. In [13], Jacobson and Kinch established the following results:For alln
≥
1,
(i)
γ
(
P
2
□
P
n
)
=
⌊
(
n
+
2
)
/
2
⌋.
(ii)
γ
(
P
3
□
P
n
)
=
⌊
(
3
n
+
4
)
/
4
⌋.
(iii)
(1)
γ
(
P
4
□
P
n
)
=
{
n
+
1
,
for
n
=
1,2
,
3,5
,
6,9
;
n
,
otherwise
.In [14], Chang and Clark established the following results:(i)
(2)
γ
(
P
5
□
P
n
)
=
{
⌊
6
n
+
6
5
⌋
,
for
n
=
2,3
,
7
;
⌊
6
n
+
8
5
⌋
,
otherwise
.
(ii)
(3)
γ
(
P
6
□
P
n
)
=
{
⌊
10
n
+
10
7
⌋
,
for
n
≥
6
and
n
≡
1
(
mod
⁡
7
)
;
⌊
10
n
+
12
7
⌋
,
otherwise
if
n
≥
4
.In [11], the authors established the following results regarding the Cartesian product of two cycles.(i)
Forn
≥
4, γ
(
C
3
□
C
n
)
=
n
-
⌊
n
/
4
⌋.
(ii)
Forn
≥
4, γ
(
C
4
□
C
n
)
=
n.
(iii)
Forn
≥
5,
(4)
γ
(
C
5
□
C
n
)
=
{
n
,
n
=
5
k
;
n
+
1
,
n
∈
{
5
k
+
1,5
k
+
2,5
k
+
4
}
.
Furthermore, γ
(
C
5
□
C
5
k
+
3
)
≤
5
(
k
+
1
).More works may be found in [8, 9, 15, 16].In the paper [17], Nandi et al. dealt with the domination number of some special types of graphs, known as cylindrical grid graphs P
m
□
C
n
,
m
≥
2
,
n
≥
3 as shown in Figure 2. An alternative way of looking at the same cylindrical grid graph is also shown in Figure 2, where the leftmost column in all figures denotes the layer (
P
m
)
0. In that paper the authors found the domination numbers as well as minimum dominating sets of the graphs P
m
□
C
n, for m
=
2,3
,
4 and for all n
≥
3 and provided bounds on γ
(
P
m
□
C
n
) for m
=
5 and for all n
≥
3. They pose an open problem for finding the domination numbers of the P
m
□
C
n, for m
≥
5.Figure 2
Two different looks of the cylindrical grid graphP
5
□
C
5.In the current paper, we deal with the above-mentioned open problem as posed in [17] and towards solving the problem, we get some partial results. We find the domination numbers as well as minimum dominating sets of the graphs P
m
□
C
n, for m
=
5 and for all n
≥
3. We also give tight bounds on γ
(
P
m
□
C
n
) for m
=
6 and for all n
≥
3. Moreover, we provide rough bounds on domination numbers of the graphs P
m
□
C
n, n
≥
3 and m
≥
7. We also point out how domination numbers and minimum dominating sets are useful for wireless sensor networks. As a brief summary, we state the following results that we prove in the subsequent sections.For alln
≥
3,
(i)
γ
(
P
5
□
C
3
)
=
4 and for n
≥
4, γ
(
P
5
□
C
n
)
=
n
+
⌊
n
/
5
⌋
+
p
n, where
(5)
p
n
=
{
0
,
i
f
n
≡
0
(
mod
⁡
10
)
;
2
,
i
f
n
≡
3,9
(
mod
⁡
10
)
;
1
,
o
t
h
e
r
w
i
s
e
.
(ii)
γ
(
P
6
□
C
3
)
=
5, γ
(
P
6
□
C
4
)
=
6, γ
(
P
6
□
C
5
)
=
8, γ
(
P
6
□
C
6
)
=
9, γ
(
P
6
□
C
7
)
=
11, and for n
>
7,
(6)
4
n
3
≤
γ
(
P
6
□
C
n
)
≤
{
⌈
10
n
7
⌉
,
for
n
≡
0,4
,
5,8
,
10,11,12
(
mod
⁡
14
)
;
⌈
10
n
7
⌉
+
1
,
otherwise
.
(iii)
Ifm
=
5
p
+
k and n
=
5
q
+
l, where p
,
q are natural numbers and k
,
l
=
0,1
,
2,3
,
4, then
(7)
⌈
m
n
5
⌉
=
5
p
q
+
k
q
+
p
l
+
⌈
k
l
5
⌉
≤
γ
(
P
m
□
C
n
)
≤
{
5
p
q
+
(
k
+
2
)
q
+
(
l
+
1
)
p
,
if
l
≠
0
5
p
q
+
(
k
+
2
)
q
,
if
l
=
0
.


## 2. Finding Minimum Dominating Sets ofP
5
□
C
n, for All n
≥
3

In this section we find the domination numbers as well as minimum dominating sets of particular cylindrical grid graphs of the formP
m
□
C
n, for all n
≥
3 and for m
=
5. To prove the main results we state the following lemmas and theorems that are proved in [17]. Throughout the paper we use the arithmetic operations of the indices over modulo n.Lemma 1 (see [17]).
Letm
≥
2. Then there exists a minimum dominating set D of P
m
□
C
n such that for every i
∈
V
(
C
n
), |
(
P
m
)
i
∩
D
|
≤
m
-
1.Lemma 2 (see [17]).
There cannot be two consecutiveP
m-layers having empty intersection with a minimum dominating set of P
m
□
C
n, for m
≥
3 and n
≥
4.Lemma 3 (see [17]).
For every dominating setD of P
m
□
C
n, the following m inequalities hold:
(8)
x
i
-
1
+
3
x
i
+
x
i
+
1
≥
n
,
∀
i
=
0
,
…
,
m
-
1
,
where x
i
=
|
(
C
n
)
i
∩
D
| for i
=
0,1
,
…
,
m
-
1 and x
-
1
=
x
m
=
0. Moreover, if x
i
-
1
+
3
x
i
+
x
i
+
1
=
n, then there does not exist any pair of vertices from (
(
C
n
)
i
-
1
∪
(
C
n
)
i
∪
(
C
n
)
i
+
1
)
∩
D such that they dominate a common vertex of (
C
n
)
i. Finally, ∑
i
=
0
m
-
1
x
i
=
|
D
|
≥
γ
(
P
m
□
C
n
).Remark 4.
The similar result holds forx
i
=
|
(
P
m
)
i
∩
D
|.Lemma 5 (see [17]).
Forn
≥
3, there exists a minimum dominating set D of P
5
□
C
n such that for every i
∈
V
(
C
n
), |
(
P
5
)
i
∩
D
|
≤
3.Lemma 6 (see [17]).
Forn
≥
5, there exists a minimum dominating set D of P
5
□
C
n such that for every i
∈
V
(
C
n
), either (a)|
(
P
5
)
i
∩
D
|
≤
2 or (b)|
(
P
5
)
i
∩
D
|
=
3 with (
P
5
)
i
-
1
∩
D
=
ϕ and (
P
5
)
i
+
1
∩
D
=
ϕ for i
∈
V
′ and |
(
P
5
)
i
∩
D
|
≤
2 for all i
∉
V
′, for some V
′
⊆
V
(
C
n
).Lemma 7 (see [17]).
Forn
≥
5, there cannot be a dominating set D with five consecutive P
5-layers having exactly one vertex in common with D.Lemma 8 (see [17]).
LetD be a minimum dominating set with the property as stated in Lemma 6. Again let (
P
5
)
i and (
P
5
)
j be two layers having two vertices in common with D and |
(
P
5
)
i
+
1
∩
D
|
≠
2, |
(
P
5
)
i
+
2
∩
D
|
≠
2
,
…
,
|
(
P
5
)
j
-
1
∩
D
|
≠
2. Then either (
a
)
|
(
P
5
)
i
+
1
∩
D
|
=
0, |
(
P
5
)
i
+
2
∩
D
|
=
3, |
(
P
5
)
i
+
3
∩
D
|
=
0, |
(
P
5
)
i
+
4
∩
D
|
=
3
,
…
,
|
(
P
5
)
j
-
1
∩
D
|
=
0, or (
b
)
j
-
i
≤
5 and |
(
P
5
)
l
∩
D
|
=
1 for all l
=
(
i
+
1
)
,
(
i
+
2
)
,
…
,
(
j
-
1
).Theorem 9 (see [17]).
Forn
≥
6, γ
(
P
5
□
C
n
)
≥
⌈
6
n
/
5
⌉.Note 1.
Let us call the collection ofP
5-layers {
(
P
5
)
k
:
k
=
i
+
1
,
i
+
2
,
…
,
j
-
1
} as a block, where i and j are as in Lemma 8.
Then|
D
|
=
(
6
n
/
5
)
+
(
(
x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
)
/
5
), where x
1
,
x
3 denotes the number of P
5-layers having 1 and 3 vertices, respectively, in common with D, x
2
′ denotes the number of blocks in which every P
5-layer has exactly one vertex in common with D, x
2
′′ denotes the number of blocks in which every P
5-layer has either 0 or 3 vertices in common with D, and x
2
0 denotes the number of blocks, where j
=
i
+
1, that is, when the block contains no P
5-layer.The above note will be useful to prove Theorem13.Theorem 10 (see [17]).
Consider the following:
(
a
)
γ
(
P
5
□
C
3
)
=
4, (
b
)
γ
(
P
5
□
C
4
)
=
5, and (
c
)
γ
(
P
5
□
C
5
)
=
7.Using the above-mentioned lemmas and theorems, we are going to prove the following main results.Theorem 11.
Forn
≥
6, γ
(
P
5
□
C
n
)
≤
n
+
⌊
n
/
5
⌋
+
p
n, where
(9)
p
n
=
{
0
,
i
f
n
≡
0
(
mod
⁡
10
)
;
2
,
i
f
n
≡
3,9
(
mod
⁡
10
)
;
1
,
o
t
h
e
r
w
i
s
e
.Proof.
Consider the dominating sets ofP
5
□
C
4 and P
5
□
C
5 as in Theorem 10 and the dominating sets of P
5
□
C
n for n
=
6,7
,
…
,
13 as shown in Figure 3.
Now using modified concatenation of the dominating set forn
=
10 repeatedly with suitably choosing one of these ten dominating sets, we get dominating sets beyond n
=
13. For example, to find a dominating set for C
5
□
P
17, we use modified concatenation of the dominating set C
5
□
P
10 with C
5
□
P
7. Again to find a dominating set for C
5
□
P
27, we use modified concatenation of the dominating set C
5
□
P
10 with C
5
□
P
17.Figure 3
Figures showing a particular dominating set forP
5
□
C
i
,
i
=
6,7
,
…
,
13, with |
D
5,6
|
=
8, |
D
5,7
|
=
9, |
D
5,8
|
=
10, |
D
5,9
|
=
12, |
D
5,10
|
=
12, |
D
5,11
|
=
14, |
D
5,12
|
=
15, and |
D
5,13
|
=
17.Corollary 12.
Forn
≥
4,
(10)
γ
(
P
5
□
C
n
)
=
{
n
+
⌊
n
5
⌋
,
i
f
n
≡
0
(
mod
⁡
10
)
;
n
+
⌊
n
5
⌋
+
1
,
i
f
n
≡
1,2
,
4,6
,
7,8
(
mod
⁡
10
)
.Proof.
Using Theorems9, 10, and 11 we get the desired result.Theorem 13.
Forn
≥
5,(1)
γ
(
P
5
□
C
n
)
=
n
+
⌊
n
/
5
⌋
+
1, if n
≡
5
(
mod
⁡
10
),
(2)
γ
(
P
5
□
C
n
)
=
n
+
⌊
n
/
5
⌋
+
2, if n
≡
3
(
mod
⁡
10
),
(3)
γ
(
P
5
□
C
n
)
=
n
+
⌊
n
/
5
⌋
+
2, if n
≡
9
(
mod
⁡
10
).Proof.
To prove the theorem we first recall Note1. Here for any minimum dominating set D with the property of P
5
□
C
n, as stated in Lemma 8, we get |
D
|
=
(
6
n
/
5
)
+
(
(
x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
)
/
5
), where the symbols are as in Note 1.
(a) Letn
≡
5
(
mod
⁡
10
); that is, n
=
5
(
2
p
+
1
), p
=
0,1
,
2
,
….
We claim that for any minimum dominating setD of P
5
□
C
n with the property as stated in Lemma 8, x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
>
0. Otherwise, there will exist a minimum dominating set D of P
5
□
C
n with the same property such that x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
0. Then x
3
=
x
2
′′
=
x
2
0
=
0 and 4
x
2
′
=
x
1 (since x
3
≥
x
2
′′
,
4
x
2
′
≥
x
1
,
x
2
0
≥
0).
HenceD has the following properties:(1)
eachP
5-layers has exactly 1 or 2 vertices in common with D,
(2)
each block has exactly4
P
5-layers; that is, without loss of generality we can write
(11)
|
(
P
5
)
i
∩
D
|
=
{
2
,
if
i
≡
0
(
mod
⁡
5
)
;
1
,
otherwise
.Since |
(
P
5
)
5
k
∩
D
|
=
2 and |
(
P
5
)
5
k
+
1
∩
D
|
=
|
(
P
5
)
5
k
+
2
∩
D
|
=
|
(
P
5
)
5
k
+
3
∩
D
|
=
|
(
P
5
)
5
k
+
4
∩
D
|
=
1 and |
(
P
5
)
5
k
+
5
∩
D
|
=
2, the number of vertices dominated by each of the vertices of (
P
5
)
5
k
+
2
∩
D and (
P
5
)
5
k
+
3
∩
D will be 4 (excluding themselves) and no vertex will be dominated by both of them simultaneously. Therefore ⋃
j
=
0
5
[
(
P
5
)
5
k
+
j
∩
D
]
=
{
(
0,5
k
)
,
(
0,5
k
+
4
)
,
(
1,5
k
+
2
)
,
(
2,5
k
)
,
(
2,5
k
+
5
)
,
(
3,5
k
+
3
)
,
(
4,5
k
+
1
)
,
(
4,5
k
+
5
)
} or {
(
0,5
k
+
1
)
,
(
0,5
k
+
5
)
,
(
1,5
k
+
3
)
,
(
2,5
k
)
,
(
2,5
k
+
5
)
,
(
3,5
k
+
2
)
,
(
4,5
k
)
,
(
4,5
k
+
4
)
} are the only two possibilities (as shown in Figure 4) of ⋃
j
=
0
5
[
(
P
5
)
5
k
+
j
∩
D
].
Now, without loss of generality let(
0,0
)
,
(
2,0
)
∈
D. Then (
0,10
p
)
,
(
2,10
p
)
∈
D.
Therefore(
1,10
p
+
2
), (
3,10
p
+
3
)
∈
D and (
0,10
p
+
2
)
∉
D; (
l
,
10
p
+
3
)
∉
D for all l
=
0,1
,
2,4. Consider (
0,10
p
+
4
)
∈
D and (
l
,
10
p
+
4
)
∉
D for all l
=
1,2
,
3,4.
Hence(
4,10
p
+
4
) cannot be dominated by the vertices of D, contradicting that D is a dominating set.
Thereforex
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
>
0.
Hence for any minimum dominating setD, |
D
|
>
6
n
/
5
=
6
(
2
p
+
1
); that is, |
D
|
≥
6
(
2
p
+
1
)
+
1. Therefore γ
(
P
5
□
C
n
)
≥
6
(
2
p
+
1
)
+
1
=
n
+
⌊
n
/
5
⌋
+
1. The rest of the proof of (a) follows from Theorem 11.
We note the following observation.
Observation
1. If  |
(
P
5
)
j
∩
D
| = |
(
P
5
)
j
+
5
∩
D
| = 2, |
(
P
5
)
j
+
1
∩
D
| = |
(
P
5
)
j
+
2
∩
D
| = |
(
P
5
)
j
+
3
∩
D
| = |
(
P
5
)
j
+
4
∩
D
| = 1, then (i) (
0
,
j
) and (
2
,
j
)
∈
D imply (
2
,
j
+
5
)
,
(
4
,
j
+
5
)
∈
D and (ii) (
2
,
j
) and (
4
,
j
)
∈
D imply (
0
,
j
+
5
)
,
(
2
,
j
+
5
)
∈
D.
(b) Letn
≡
3
(
mod
⁡
10
); that is, n
=
10
p
+
3.
We claim thatx
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
>
2 for any minimum dominating set D of P
5
□
C
n with the property as stated in Lemma 8.
If possible let there exist a minimum dominating setD with the property as stated in Lemma 8 and x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
0. Then x
2
′′
=
x
3
=
0 and x
1
=
4
x
2
′
,
x
2
0
=
0 which will be impossible since n
≢
0
(
mod
⁡
5
).
If possible let there exist a minimum dominating setD with the property as stated in Lemma 8 and x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
1. Then x
2
′′
=
x
3 and x
2
0
=
0. Therefore x
2
′′
=
x
3
=
1, x
1
=
4
x
2
′, and x
2
0
=
0 or x
2
′′
=
x
3
=
x
2
0
=
0 and x
1
=
4
x
2
′
-
1.
Now ifx
2
′′
=
x
3
=
1 and x
1
=
4
x
2
′ then let x
0 denote the number of P
5-layers having 0 vertices in common with D and x
0
=
x
2
′′
+
x
3
=
2.
By Lemma8, x
2
=
x
0
+
x
2
′
+
x
2
′′ is the number of P
5-layers having 2 vertices in common with D and n
=
x
0
+
x
1
+
x
2
+
x
3
=
x
0
+
x
1
+
x
2
0
+
x
2
′
+
x
2
′′
+
x
3
=
2
+
4
x
2
′
+
x
2
′
+
1
+
1
=
5
x
2
′
+
4
≢
3
(
mod
⁡
5
) which is a contradiction.
Again ifx
2
′′
=
x
3
=
0 and x
1
=
4
x
2
′
-
1 then n
=
x
0
+
x
1
+
x
2
0
+
x
2
′
+
x
2
′′
+
x
3
=
4
x
2
′
-
1
+
x
2
′
≢
3
(
mod
⁡
5
), which is also a contradiction.
If possible let there exist a minimum dominating setD with the property as stated in Lemma 8 and x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
2
…
(
A
). Then x
2
′′
=
x
3 (otherwise, x
3
≠
x
2
′′ implies x
3
-
x
2
′′
≥
1 and x
3
≥
1, contradicting (
A
)) and x
2
0
=
0.
Now there are the following three cases.
Case
1.Considerx
3
=
x
2
′′
=
x
2
0
=
0 and x
1
=
4
x
2
′
-
2.
Sincex
3
=
x
2
′′
=
x
2
0
=
0 each block contains only those P
5-layers which have exactly one vertex in common with D.
Again sincex
1
=
4
x
2
′
-
2, there are two sub cases.
Subcase
1.1. When only one block contains two P
5-layers and other block contains four P
5-layers then without loss of generality let |
(
P
5
)
j
∩
D
|
=
2 for j
=
0,5
,
10
,
…
,
10
p and |
(
P
5
)
j
∩
D
|
=
1, otherwise. Now (
0,0
)
,
(
2,0
)
∈
D or (
2,0
)
,
(
4,0
)
∈
D. If possible let (
0,0
)
,
(
2,0
)
∈
D. Then (
0,10
p
)
,
(
2,10
p
)
∈
D and (
j
,
10
p
)
∉
D for j
=
1,3
,
4. But this is not possible since |
(
P
5
)
10
p
+
1
∩
D
|
=
|
(
P
5
)
10
p
+
2
∩
D
|
=
1 and (
0,10
p
+
3
)
,
(
2,10
p
+
3
)
∈
D and (
j
,
10
p
+
3
)
∉
D for j
=
1,3
,
4. Note that (
P
5
)
10
p
+
3
=
(
P
5
)
0.
Similar contradiction will be arrived for(
2,0
)
,
(
4,0
)
∈
D.
Subcase
1.2. When only two blocks contain three P
5-layers and other blocks contain four P
5-layers then if(i)
the blocks containing threeP
5-layers, each occurs consecutively then without loss of generality let |
(
P
5
)
j
∩
D
|
=
2 for j
=
0,5
,
10
,
…
,
10
p
-
5,10
p
-
1 and |
(
P
5
)
j
∩
D
|
=
1, otherwise. Now if (
0,0
)
,
(
2,0
)
∈
D then (
2,10
p
-
5
)
,
(
4,10
p
-
5
)
∈
D
⇒
(
1,10
p
+
1
)
,
(
3,10
p
-
3
)
∈
D
⇒
(
0,10
p
-
1
)
,
(
4,10
p
-
1
)
∈
D which is a contradiction.Similar contradiction will be arrived for (
2,0
)
,
(
4,0
)
∈
D,
(ii)
the blocks containing threeP
5-layers do not occur consecutively then among them one of the blocks consist of j
+
1
,
j
+
2
,
j
+
3
P
5-layer for some j and either (
a
)
(
0
,
j
)
,
(
2
,
j
)
∈
D and (
2
,
j
+
4
)
,
(
4
,
j
+
4
)
∈
D or (
b
)
(
2
,
j
)
,
(
4
,
j
)
∈
D and (
0
,
j
+
4
)
,
(
2
,
j
+
4
)
∈
D. In each case, we arrive at a contradiction. Hence we conclude that Case 1 cannot occur.
Case
2.Considerx
3
=
x
2
′′
=
1
,
x
2
0
=
0, and x
1
=
4
x
2
′
-
1.
In this case only two blocks contain threeP
5-layers and other blocks contain four P
5-layers. Among these two blocks one contains only those P
5-layers which have exactly one vertex in common with D and other block contains three layers whose number of vertices are 0,3
,
0 consecutively.
Now we note the following observations.
Observation
2. If |
(
P
5
)
j
∩
D
|
=
|
(
P
5
)
j
+
4
∩
D
|
=
2
,
|
(
P
5
)
j
+
2
∩
D
|
=
3, and |
(
P
5
)
j
+
1
∩
D
|
=
|
(
P
5
)
j
+
3
∩
D
|
=
0 then (
0
,
j
)
,
(
2
,
j
)
∈
D implies (
0
,
j
+
4
)
,
(
2
,
j
+
4
)
∈
D and (
2
,
j
)
,
(
4
,
j
)
∈
D implies (
2
,
j
+
4
)
,
(
4
,
j
+
4
)
∈
D.
Observation
3. If |
(
P
5
)
j
∩
D
|
=
|
(
P
5
)
j
+
4
∩
D
|
=
2
,
|
(
P
5
)
j
+
1
∩
D
|
=
|
(
P
5
)
j
+
2
∩
D
|
=
|
(
P
5
)
j
+
3
∩
D
|
=
1 then (
0
,
j
)
,
(
2
,
j
)
∈
D implies (
0
,
j
+
4
)
,
(
2
,
j
+
4
)
∈
D or (
0
,
j
+
4
)
,
(
3
,
j
+
4
)
∈
D and (
2
,
j
)
,
(
4
,
j
)
∈
D implies (
2
,
j
+
4
)
,
(
4
,
j
+
4
)
∈
D or (
1
,
j
+
4
)
,
(
4
,
j
+
4
)
∈
D.
Without loss of generality we now assume that|
(
P
5
)
0
∩
D
|
=
|
(
P
5
)
4
∩
D
|
=
2
,
|
(
P
5
)
1
∩
D
|
=
|
(
P
5
)
2
∩
D
|
=
|
(
P
5
)
3
∩
D
|
=
1. Therefore by Observation 2 and Observation 1 in Case (a) we have either (
0,0
)
,
(
2,0
)
∈
D and (
2,4
)
,
(
4,4
)
∈
D or (
2,0
)
,
(
4,0
)
∈
D and (
0,4
)
,
(
2,4
)
∈
D which is again a contradiction by Observation 3.
Case
3.Considerx
3
=
x
2
′′
=
2
,
x
2
0
=
0, and x
1
=
4
x
2
′.
In this case only two blocks contain threeP
5-layers and other blocks contain four P
5-layers and these two blocks contain three layers whose number of vertices is 0,3
,
0 consecutively. Therefore by the Observation 2, as in Case 2, we arrive at a contradiction.
Then|
D
|
=
(
6
n
/
5
)
+
(
(
x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
)
/
5
)
>
(
(
60
p
+
18
)
/
5
)
+
(
2
/
5
)
=
12
p
+
4.
Therefore|
D
|
≥
12
p
+
5
=
10
p
+
3
+
2
p
+
2
=
n
+
⌊
n
/
5
⌋
+
2. This completes the proof of (
b
).
(c) Letn
≡
9
(
mod
⁡
10
); that is, n
=
10
p
+
9.
We claim that for any minimum dominating setD of P
5
□
C
n with the property as stated in Lemma 8, x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
>
1.
If possible letx
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
0. Then as in (b), n
≢
0
(
mod
⁡
5
). As a result, we have the same contradiction.
If possible letx
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
=
1. Then x
3
=
x
2
′′ and therefore the following two cases arise.
Case
1.Considerx
3
=
x
2
′
′
=
x
2
0
=
0 and x
1
=
4
x
2
′
-
1.
Case
2.Considerx
3
=
x
2
′′
=
1, x
1
=
4
x
2
′, and x
2
0
=
0.
In these two cases contradiction can be shown similarly as in (b), wheren
≡
3
(
mod
⁡
10
).
Hence|
D
|
=
(
6
n
/
5
)
+
(
(
x
3
+
2
(
x
3
-
x
2
′′
)
+
(
4
x
2
′
-
x
1
)
+
4
x
2
0
)
/
5
)
>
(
(
60
p
+
54
)
/
5
)
+
(
1
/
5
)
=
12
p
+
11.
Therefore|
D
|
≥
12
p
+
12
=
n
+
⌊
n
/
5
⌋
+
2. This completes the proof of (c).Figure 4
The only two possible configurations of the vertices of a minimum dominating set of the graphP
5
□
C
n in four consecutive layers P
i
,
P
i
+
1
,
P
i
+
2, and P
i
+
3.Remark 14.
Forn
≥
3 and n
≠
7,
(12)
γ
(
P
5
□
C
n
)
=
{
γ
(
P
5
□
P
n
)
-
1
,
when
n
≡
0,2
,
4,7
,
8
(
mod
⁡
10
)
;
γ
(
P
5
□
P
n
)
,
otherwise
,
and γ
(
P
5
□
C
7
)
=
γ
(
P
5
□
P
7
). Moreover, for n
≥
3, γ
(
P
5
□
C
n
)
>
γ
(
P
5
)
·
γ
(
C
n
)
=
2
·
⌈
n
/
3
⌉.


## 3. Bounds on Domination Numbers ofP
6
□
C
n for All n
≥
3

In this section we give upper and lower bounds of the domination numbers ofP
6
□
C
n. Towards this direction, we first prove the following lemmas.Lemma 15.
Letn
≥
4. Then there exists a minimum dominating set D of P
6
□
C
n with |
(
P
6
)
i
∩
D
|
≤
4
∀
i.Proof.
LetD be a minimum dominating set of P
6
□
C
n with the property |
(
P
6
)
i
∩
D
|
≤
5
∀
i. Such a D exists by Lemma 1. Suppose further that |
(
P
6
)
j
∩
D
|
=
5 for k many P
6 layers.
Assume that|
(
P
6
)
i
∩
D
|
=
5 for some i, then |
(
P
6
)
i
+
1
∩
D
|
≤
2; otherwise D
′
=
D
∖
[
(
P
6
)
i
∪
(
P
6
)
i
+
1
]
∪
{
(
0
,
i
)
,
(
1
,
i
+
2
)
,
(
2
,
i
-
1
)
,
(
3
,
i
+
1
)
,
(
4
,
i
-
1
)
,
(
5
,
i
)
,
(
5
,
i
+
2
)
} is a dominating set with |
D
′
|
<
|
D
|, which is a contradiction.
Similar contradiction shows that|
(
P
6
)
i
-
1
∩
D
|
≤
2. Now construct D
′′
=
D
∖
(
P
6
)
i
∪
{
(
0
,
i
)
,
(
2
,
i
-
1
)
,
(
2
,
i
+
1
)
,
(
4
,
i
)
,
(
5
,
i
)
}. Then |
D
′′
|
≤
|
D
| and hence D
′′ is a minimum dominating set with k
-
1 many P
6 layers having 5 vertices in common with D
′′. Repeating this construction we get the desired minimum dominating set and hence the lemma follows.Lemma 16.
For any minimum dominating setD, |
(
P
6
)
i
∩
D
|
=
1
=
|
(
P
6
)
i
+
1
∩
D
|
∀
i implies |
(
P
6
)
i
+
2
∩
D
|
≥
2 and |
(
P
6
)
i
-
1
∩
D
|
≥
2.Proof.
The proof of the lemma follows from Remark4.Lemma 17.
Forn
≥
4, there exists a minimum dominating set D of P
6
□
C
n with the property (i) if |
(
P
6
)
i
∩
D
|
=
1, |
(
P
6
)
i
+
1
∩
D
|
=
1, |
(
P
6
)
i
+
2
∩
D
|
=
2 for some i, then |
(
P
6
)
i
+
3
∩
D
|
≥
1;
(ii) if|
(
P
6
)
i
∩
D
|
=
2, |
(
P
6
)
i
+
1
∩
D
|
=
1, |
(
P
6
)
i
+
2
∩
D
|
=
1 for some i, then |
(
P
6
)
i
-
1
∩
D
|
≥
1 and (iii) |
(
P
6
)
i
∩
D
|
≤
4
∀
i.Proof.
LetD be a minimum dominating set of P
6
□
C
n with the property |
(
P
m
)
i
∩
D
|
≤
4
∀
i. Such a D exists by Lemma 15. Let x
i
=
|
(
P
6
)
i
∩
D
|
,
i
=
0,1
,
…
,
n
-
1.
Whenn
=
4, then x
i
=
1
,
x
i
+
1
=
1, and x
i
+
2
=
2 imply that x
i
+
3
≥
1 since by Remark 4, x
i
-
1
+
3
x
i
+
x
i
+
1
≥
6. Note that in this case, (
P
6
)
i
-
1
=
(
P
6
)
i
+
3 and hence x
i
-
1
=
x
i
+
3.
Letn
≥
5. If x
i
=
1
,
x
i
+
1
=
1
,
x
i
+
2
=
2, and x
i
+
3
=
0 then x
i
+
4
=
4. Also, x
i
+
5
≤
3; otherwiseD
′
=
D
∖
[
(
P
6
)
i
+
4
∪
(
P
6
)
i
+
5
]
∪
{
(
0
,
i
+
4
)
,
(
1
,
i
+
6
)
,
(
2
,
i
+
3
)
,
(
2
,
i
+
5
)
,
(
4
,
i
+
4
)
,
(
4
,
i
+
6
)
,
(
5
,
i
+
4
)
} will be a dominating set with |
D
′
|
<
|
D
|, a contradiction. Clearly, (
0
,
i
+
1
)
,
(
5
,
i
+
1
)
∉
D. Also (
1
,
i
+
1
)
,
(
4
,
i
+
1
)
∉
D, because if (
1
,
i
+
1
)
∈
D, then (
0
,
i
+
2
)
∈
D or (
1
,
i
+
2
)
∈
D, each of which will be a contradiction, since (
3
,
i
+
1
)
,
(
4
,
i
+
1
) and (
5
,
i
+
1
) cannot be dominated by one vertex from (
P
6
)
i and one vertex from (
P
6
)
i
+
2. Similar contradiction will be arrived for (
4
,
i
+
1
)
∈
D. Let (
2
,
i
+
1
)
∈
D. Then (
0
,
i
+
2
)
,
(
4
,
i
+
2
)
∈
D. Hence we have (
1
,
i
+
4
)
,
(
2
,
i
+
4
)
,
(
3
,
i
+
4
)
,
(
5
,
i
+
4
)
∈
D. Therefore we can construct D
′
=
[
D
∖
{
(
2
,
i
+
4
)
,
(
3
,
i
+
4
)
}
]
∪
{
(
2
,
i
+
3
)
,
(
3
,
i
+
5
)
}. In a similar way we can construct D
′ when (
3
,
i
+
2
)
∈
D. Repeating this construction for all i for which x
i
=
x
i
+
1
=
1
,
x
i
+
2
=
2
,
x
i
+
3
=
0, and x
i
-
1
=
0, x
i
=
2, x
i
+
1
=
1, x
i
+
2
=
1, we get a minimum dominating set with the desired property.Lemma 18.
Consider a minimum dominating setD of P
6
□
C
n with the property as stated in Lemma 17. Let x
i
=
|
(
P
6
)
i
∩
D
|
,
i
=
0,1
,
…
,
n
-
1.
Then(
x
i
/
2
)
+
x
i
+
1
+
x
i
+
2
+
(
(
x
i
+
3
)
/
2
)
≥
4.Proof.
Case
1. Consider x
i
+
1
=
0; this implies x
i
+
2
≥
2 (since x
i
≤
4).
Subcase  1
.
1. Consider x
i
+
2
=
2; this implies x
i
=
4.
Subcase  1.2.Considerx
i
+
2
=
3; this implies x
i
≥
3.
Subcase  1.3.Considerx
i
+
2
=
4.
For every subcase we get the desired result.
Case
2. Considerx
i
+
1
=
1; this implies x
i
+
2
≥
1.
Subcase
2
.1. Considerx
i
+
2
=
1; this implies x
i
≥
2
,
x
i
+
3
≥
2.
Subcase  2.2. Considerx
i
+
2
=
2; this implies x
i
≥
1 which implies x
i
+
x
i
+
3
≥
2 (since if x
i
=
1 then by Lemma 17  x
i
+
3
≥
1).
Subcase  2.3. Considerx
i
+
2
≥
3.
For every subcase we get the desired result.
Case
3. Consider x
i
+
1
=
2.
Subcase  3
.1. Considerx
i
+
2
=
0; this implies x
i
+
3
≥
4.
Subcase  3.2. Considerx
i
+
2
=
1; this implies x
i
+
3
≥
1 which implies x
i
+
x
i
+
3
≥
2 (by Lemma 17).
Subcase  3.3. Considerx
i
+
2
≥
2.
For every subcase we get the desired result.
Case
4. Consider x
i
+
1
=
3.
Subcase 4.1. Considerx
i
+
2
=
0; this implies x
i
+
3
≥
3 as in Subcase 1.2.
Subcase 4.2. Considerx
i
+
2
≥
1.
For every subcase we get the desired result.
Case
5. Consider x
i
+
1
=
4.
In this case also(
x
i
/
2
)
+
x
i
+
1
+
x
i
+
2
+
(
x
i
+
3
/
2
)
≥
4.Based on Lemma17, we prove the following theorem which provides a lower bound on γ
(
P
6
□
C
n
), for n
≥
3.Theorem 19.
Forn
≥
3, γ
(
P
6
□
C
n
)
≥
4
n
/
3.Proof.
Case
1. When n
=
3, for any dominating set D
,
|
D
|
≥
18
/
5
>
3 (since the total number of vertices is 6
×
3
=
18 and one vertex of D can dominate at most 5 vertices including itself). Therefore |
D
|
≥
4
=
(
(
4
×
3
)
/
3
). Hence the theorem is true for n
=
3.
Case
2. For n
≥
4 consider a minimum dominating set D of P
6
□
C
n with the property as stated in Lemma 17. Then (
x
i
/
2
)
+
x
i
+
1
+
x
i
+
2
+
(
x
i
+
3
/
2
)
≥
4
∀
i
=
0,1
,
…
,
n
-
1. Therefore ∑
i
=
0
n
-
1
{
(
x
i
/
2
)
+
x
i
+
1
+
x
i
+
2
+
(
x
i
+
3
/
2
)
}
≥
4
n that implies 3
∑
i
=
0
n
-
1
x
i
≥
4
n that implies ∑
i
=
0
n
-
1
x
i
≥
4
n
/
3; that is, |
D
|
≥
4
n
/
3, hence the theorem.Remark 20.
For simplification, henceforth, in all the figures, we are only considering the grid structure avoiding the circular arks to represent the circular grid as shown in Figure5.Figure 5
Dominating set forP
6
□
C
4 and its representation in grid form without circular arks.The following theorem provides domination numbers and dominating sets for some particular cyclic grid graphs which will help in providing the upper bounds forγ
(
P
6
□
C
n
), for n
>
7 as addressed in Theorem 23.Theorem 21.
Consider the following:
(
a
)   γ
(
P
6
□
C
3
)
=
5, (
b
)   γ
(
P
6
□
C
4
)
=
6, (
c
)   γ
(
P
6
□
C
5
)
=
8, (
d
)   γ
(
P
6
□
C
6
)
=
9, and (
e
)   γ
(
P
6
□
C
7
)
=
11.Proof.
(a) A dominating set forP
6
□
C
3 is D
6,3
=
{
(
0,1
)
,
(
2,0
)
,
(
2,2
)
,
(
4,1
)
,
(
5,1
)
}, as shown in Figure 6. As |
D
6,3
|
=
5, γ
(
P
6
□
C
3
)
≤
5. We want to show γ
(
P
6
□
C
3
)
=
5.
If possible let there exist a dominating setD, of P
6
□
C
3 with |
D
|
≤
4.
Letx
i
=
|
(
C
3
)
i
∩
D
|
,
i
=
0,1
,
2,3
,
4,5.
Therefore,(i)
x
0
+
x
1
+
⋯
+
x
5
≤
4,
(ii)
3
x
0
+
x
1
≥
3,
(iii)
x
0
+
3
x
1
+
x
2
≥
3,
(iv)
x
1
+
3
x
2
+
x
3
≥
3,
(v)
x
2
+
3
x
3
+
x
4
≥
3,
(vi)
x
3
+
3
x
4
+
x
5
≥
3,
(vii)
x
4
+
3
x
5
≥
3.
We claim thatx
0
≥
1; otherwise, if possible let x
0
=
0; then x
1
≥
3.
Therefore,x
2
+
x
3
+
x
4
+
x
5
≤
1.
This impliesx
4
+
x
5
≤
1 and hence x
5
≥
1 (from (vii)).
Therefore,x
5
=
1 and then x
1
+
x
5
≥
4 implies x
0
=
x
2
=
x
3
=
x
4
=
0, contradicting (v), hence the claim.
Similarly, we can show thatx
5
≥
1.
Therefore,x
1
+
x
2
+
x
3
+
x
4
≤
2
⇒
x
3
≥
1
,
x
2
≥
1 (using (iv) and (v)).
Hence,x
0
=
x
2
=
x
3
=
x
5
=
1 which implies x
1
=
x
4
=
0, contradicting (iii).
Therefore,γ
(
P
6
□
C
3
)
=
5.
(b) A dominating set forP
6
□
C
4 is D
6,4
=
{
(
0,3
)
,
(
1,1
)
,
(
2,3
)
,
(
3,0
)
,
(
4,2
)
,
(
5,0
)
}, as shown in Figure 6. As |
D
6,4
|
=
6, γ
(
P
6
□
C
4
)
≤
6. We want to show γ
(
P
6
□
C
4
)
=
6.
If possible let there exist a dominating setD of P
6
□
C
4 with |
D
|
≤
5.
Letx
i
=
|
(
C
4
)
i
∩
D
|
,
i
=
0,1
,
2,3
,
4,5.
Therefore,(i)
x
0
+
x
1
+
⋯
+
x
5
≤
5,
(ii)
3
x
0
+
x
1
≥
4,
(iii)
x
0
+
3
x
1
+
x
2
≥
4,
(iv)
x
1
+
3
x
2
+
x
3
≥
4,
(v)
x
2
+
3
x
3
+
x
4
≥
4,
(vi)
x
3
+
3
x
4
+
x
5
≥
4,
(vii)
x
4
+
3
x
5
≥
4.
We claim thatx
0
≥
1; otherwise, if possible let x
0
=
0. Then x
1
≥
4, which implies x
2
+
x
3
+
x
4
+
x
5
≤
1, contradicting (vii), hence the claim.
Therefore,x
0
≥
1. Similarly, we can show that x
5
≥
1. Next we claim that x
1
≥
1. If possible let x
1
=
0. Therefore, x
0
+
x
2
≥
4
⇒
x
3
+
x
4
+
x
5
≤
1, contradicting (vii), hence the claim. Therefore x
1
≥
1. Similarly, x
5
,
x
3
,
x
4
≥
1, contradicting (i).
Therefore,γ
(
P
6
□
C
4
)
=
6.
(c) A dominating set forP
6
□
C
5 is D
6,5
=
{
(
0,3
)
,
(
0,4
)
,
(
1,1
)
,
(
2,3
)
,
(
3,0
)
,
(
4,2
)
,
(
5,0
)
,
(
5,4
)
} as shown in Figure 6.
As|
D
6,5
|
=
8, γ
(
P
6
□
C
5
)
≤
8. We want to show γ
(
P
6
□
C
5
)
=
8.
If possible let there exist a dominating setD of P
6
□
C
5 with |
D
|
≤
7.
Letx
i
=
|
(
C
4
)
i
∩
D
|
,
i
=
0,1
,
2,3
,
4,5.
Therefore,(i)
x
0
+
x
1
+
⋯
+
x
5
≤
7,
(ii)
3
x
0
+
x
1
≥
5,
(iii)
x
0
+
3
x
1
+
x
2
≥
5,
(iv)
x
1
+
3
x
2
+
x
3
≥
5,
(v)
x
2
+
3
x
3
+
x
4
≥
5,
(vi)
x
3
+
3
x
4
+
x
5
≥
5,
(vii)
x
4
+
3
x
5
≥
5.
We claim thatx
0
≥
1; otherwise, if possible let x
0
=
0. Then x
1
≥
5, which implies x
2
+
x
3
+
x
4
+
x
5
≤
2.
From (vii) we get,x
5
=
2 and x
4
=
0; hence, x
2
=
x
3
=
0, a contradiction.
Similarly, we can show thatx
5
≥
1. Now we claim that x
1
≥
1; otherwise, x
0
+
x
2
≥
5, which implies x
3
+
x
4
+
x
5
≤
2. Therefore, from (vii), x
5
=
2 and x
4
=
0
=
x
3, contradicting (vi). Similarly, x
4
,
x
2
,
x
3
≥
1. Next we claim that x
0
≥
2; otherwise, x
0
=
1 and x
1
≥
2. Therefore, x
0
=
x
2
=
x
3
=
x
4
=
x
5
=
1 and x
1
=
2, contradicting (vii). Similarly, x
5
≥
2, contradicting (i).
(d) A dominating set forP
6
□
C
6 is D
6,6
=
{
(
0,0
)
,
(
0,4
)
,
(
1,2
)
,
(
2,5
)
,
(
3,1
)
,
(
3,3
)
,
(
4,0
)
,
(
5,2
)
,
(
5,4
)
} as shown in Figure 7. As |
D
6,6
|
=
9, γ
(
P
6
□
C
6
)
≤
9. We want to show γ
(
P
6
□
C
6
)
=
9.
If possible let there exist a dominating setD of P
6
□
C
6 with |
D
|
≤
8.
Letx
i
=
|
(
C
4
)
i
∩
D
|
,
i
=
0,1
,
2,3
,
4,5.
Therefore,(i)
x
0
+
x
1
+
⋯
+
x
5
≤
8,
(ii)
3
x
0
+
x
1
≥
6,
(iii)
x
0
+
3
x
1
+
x
2
≥
6,
(iv)
x
1
+
3
x
2
+
x
3
≥
6,
(v)
x
2
+
3
x
3
+
x
4
≥
6,
(vi)
x
3
+
3
x
4
+
x
5
≥
6,
(vii)
x
4
+
3
x
5
≥
6.
We claim thatx
0
≥
1; otherwise, if possible let x
0
=
0. Then x
1
≥
6, which implies x
4
+
x
5
≤
2 and hence x
5
=
2 (by (vii)).
Hence,x
0
=
x
2
=
x
3
=
x
4
=
0, a contradiction.
Therefore,x
0
≥
1. Similarly we can show that x
5
≥
1.
Now we claim thatx
1
≥
1; otherwise, x
0
+
x
2
≥
6, which implies that x
4
+
x
5
≤
2. Therefore, x
5
=
2 (by (vii)) and hence x
1
=
x
3
=
x
4
=
0, contradicting (vi). Hence, x
1
≥
1. Similarly x
2
,
x
3
,
x
4
≥
1.
Next we claim thatx
0
≥
2; otherwise, let x
0
=
1. Then x
1
≥
3.
Therefore,x
0
=
x
2
=
x
3
=
x
4
=
x
5
=
1 and hence x
1
=
3 which contradicts (vii).
Hence,x
0
≥
2. Similarly, x
5
≥
2. Therefore, x
0
=
x
5
=
2 and x
1
=
x
2
=
x
3
=
x
4
=
1, which contradicts (iv). Hence, γ
(
P
6
□
C
6
)
=
9.
(e) A dominating set forP
6
□
C
7 is D
6,7
=
{
(
0,0
)
,
(
0,4
)
,
(
1,2
)
,
(
2,5
)
,
(
2,6
)
,
(
3,1
)
,
(
3,3
)
,
(
4,0
)
,
(
4,6
)
(
5,2
)
,
(
5,4
)
} as shown in Figure 7. As |
D
6,7
|
=
11, γ
(
P
6
□
C
7
)
≤
11. We want to show γ
(
P
6
□
C
7
)
=
11.
If possible let there exist a dominating setD of P
6
□
C
7 with |
D
|
≤
10.
Letx
i
=
|
(
C
4
)
i
∩
D
|
,
i
=
0,1
,
2,3
,
4,5.
Therefore,(i)
x
0
+
x
1
+
⋯
+
x
5
≤
10,
(ii)
3
x
0
+
x
1
≥
7,
(iii)
x
0
+
3
x
1
+
x
2
≥
7,
(iv)
x
1
+
3
x
2
+
x
3
≥
7,
(v)
x
2
+
3
x
3
+
x
4
≥
7,
(vi)
x
3
+
3
x
4
+
x
5
≥
7,
(vii)
x
4
+
3
x
5
≥
7.
By similar arguments, as in (d) we can prove,x
0
,
x
5
≥
2 and x
1
,
x
2
,
x
3
,
x
4
≥
1.
We claim thatx
1
≤
2. If possible let x
1
≥
3. Then x
0
=
x
5
=
2
,
x
1
=
3, and x
2
=
x
3
=
x
4
=
1, contradicting (v), which implies that x
1
≤
2. Similarly, x
2
,
x
3
,
x
4
≤
2.
Next we claim thatx
0
≤
2; otherwise, let x
0
≥
3. Now clearly x
0
≤
3 and hence x
0
=
3.
Hence, we have the following cases:(
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,1
,
1,1
,
2
) or (
1,2
,
1,1
,
2
) or (
1,1
,
2,1
,
2
) or (
1,1
,
1,2
,
2
) or (
1,1
,
1,1
,
3
) and each of the cases lead to contradictions.
Therefore,x
0
=
2. Similarly, we can show that x
5
=
2.
Hence the possibilities are(
x
1
,
x
2
,
x
3
,
x
4
)
=
(
1,1
,
2,2
) or (
2,2
,
1,1
) or (
2,1
,
1,2
) or (
1,2
,
2,1
) or (
2,1
,
2,1
) or (
1,2
,
1,2
).
It is easy to show that first three cases lead to contradictions.
Hence the possibilities become(
x
0
,
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,1
,
2,2
,
1,2
) or (
2,2
,
1,2
,
1,2
) or (
2,1
,
2,1
,
2,2
).
If possible let there exist a dominating setD with (
x
0
,
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,1
,
2,2
,
1,2
).
Without loss of generality, let(
0,0
)
∈
D.
Therefore,(
0,1
)
,
(
0,2
)
,
(
0,5
)
,
(
0,6
)
∉
D.
Without loss of generality, let(
0,3
)
∈
D. Therefore (
1,5
)
∈
D. This implies (
2,1
)
,
(
2,2
)
∈
D.
Hence,(
3,4
)
,
(
3,6
)
∈
D; then, (
4,0
), (
4,3
), (
4,4
), (
4,5
), (
4,6
)
∉
D.
Now if(
4,1
)
∈
D, then, (
5,3
)
,
(
5,5
)
,
∈
D. But then (
5,0
) is not dominated by any vertex of D as shown in Figure 8.
And if(
4,2
)
∈
D, then, (
5,0
)
,
(
5,5
)
,
∈
D. But then (
5,3
) is not dominated by any vertex of D.
Hence there does not exist any dominating setD with (
x
0
,
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,1
,
2,2
,
1,2
).
By similar manner we can show there does not exist any dominating set with(
x
0
,
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,1
,
2,1
,
2,2
), as shown in Figure 8.
Again there does not exist any dominating setD with (
x
0
,
x
1
,
x
2
,
x
3
,
x
4
,
x
5
)
=
(
2,2
,
1,2
,
1,2
) as this case is similar as the above case. Hence, γ
(
P
6
□
C
7
)
=
11.Figure 6
Dominating sets forP
6
□
C
3, P
6
□
C
4, and P
6
□
C
5.Figure 7
Dominating sets forP
6
□
C
6 and P
6
□
C
7.Figure 8
Figures show nonpossibility of dominating sets in some cases.The following theorem provides bounds for dominating sets that will help in proving the main Theorem23.Theorem 22.
Consider the following:
(
i
)
γ
(
P
6
□
C
8
)
≤
12, (
ii
)
γ
(
P
6
□
C
9
)
≤
14, (
iii
)
γ
(
P
6
□
C
10
)
≤
15, (
iv
)
γ
(
P
6
□
C
11
)
≤
16, (
v
)
γ
(
P
6
□
C
12
)
≤
18, (
vi
)
γ
(
P
6
□
C
13
)
≤
20, (
vii
)
γ
(
P
6
□
C
14
)
≤
20, (
viii
)
γ
(
P
6
□
C
15
)
≤
23, (
ix
)
γ
(
P
6
□
C
16
)
≤
24, (
x
)
γ
(
P
6
□
C
17
)
≤
26, (
xi
)
γ
(
P
6
□
C
18
)
≤
26, (
xii
)
γ
(
P
6
□
C
19
)
≤
28, (
xiii
)
γ
(
P
6
□
C
20
)
≤
30, (
xiv
)
γ
(
P
6
□
C
21
)
≤
31, (
xv
)
γ
(
P
6
□
C
22
)
≤
31, (
xvi
)
γ
(
P
6
□
C
23
)
≤
34, (
xvii
)
γ
(
P
6
□
C
24
)
≤
35, (
xviii
)
γ
(
P
6
□
C
25
)
≤
36, (
xix
)
γ
(
P
6
□
C
26
)
≤
38, and (
xx
)
γ
(
P
6
□
C
27
)
≤
40.Proof.
Dominating sets for each of the cases are shown in Figures12, 13, 14, 15, 16, 17, and 18.Theorem 23.
Forn
>
7,
(13)
γ
(
P
6
□
C
n
)
≤
{
⌈
10
n
7
⌉
,
f
o
r
n
≡
0,4
,
5,8
,
10,11,12
(
mod
⁡
14
)
;
⌈
10
n
7
⌉
+
1
,
o
t
h
e
r
w
i
s
e
.Proof.
For3
≤
n
≤
27, the above inequalities have already been proved in Theorems 21 and 22. For n
≥
28 one can easily find a dominating set for γ
(
P
6
□
C
n
) using repeated modified concatenation between the dominating set for γ
(
P
6
□
C
14
) with dominating set for γ
(
P
6
□
C
n
-
14
).The following theorem provides a lower bound forγ
(
P
6
□
C
n
), for n
>
7.Theorem 24.
Forn
>
7, if there exists a minimum dominating set D with |
(
P
6
)
i
∩
D
|
=
1 or 2 for all i, then γ
(
P
6
□
C
n
)
≥
⌈
10
n
/
7
⌉ resulting γ
(
P
6
□
C
n
)
=
⌈
10
n
/
7
⌉
+
0 or 1, accordingly.Proof.
It is enough to show that, for a dominating setD with |
(
P
6
)
i
∩
D
|
=
1
or
2 for all i, it holds that |
D
|
≥
⌈
10
n
/
7
⌉.
We say the configuration of the typek
1
k
2
k
3
… occurs in a dominating set D, where k
1
,
k
2
,
k
3
,
… are 1 or 2, if there are consecutive columns in the graph with k
1
,
k
2
,
k
3
… many common vertex (or vertices) with D.
We have the following observations which can be verified considering all possible cases (we omit the verification because it has several cases and subcases and require similar types of arguments).(1)
There cannot be three consecutive columns with only one vertex common withD; that is, the configuration of the type 111 cannot occur in D. This is clear from Remark 4.
(2)
If the configuration of the type2112112 occurs, then just before and after these seven columns the configuration of the type 22 should occur; that is, the configuration of the type 22211211222 should occur where the previous configuration occurs inside this.
(3)
If there are two configurations of the type2112 which occurs and between these two configurations only 212 type configuration occurs then the configuration of the type 212 occurs at least twice.
(4)
The configuration of the type211221122112 cannot occur.
Now let there be2
x
+
y many configurations of the type 2112 occur where 2
x many configurations occur in x many pair and y many occur without pairing. Also let z many configurations of the type 22 occur and t many configuration of the type 212 occur.
Then,z
≥
x and t
≥
2
(
x
+
y
-
z
). Now the number of columns which have one vertex in common with D is 2
(
2
x
+
y
)
+
t and the number of columns which have two vertices in common with D is 2
x
+
y
+
z
+
t.
Therefore,n
=
2
(
2
x
+
y
)
+
t
+
(
2
x
+
y
+
z
+
t
) and |
D
|
=
2
(
2
x
+
y
)
+
t
+
2
(
2
x
+
y
+
z
+
t
).
Hence,7
|
D
|
-
10
n
=
4
(
2
x
+
y
+
z
+
t
)
-
3
(
2
(
2
x
+
y
)
+
t
)
=
-
4
x
-
2
y
+
t
+
4
z
=
2
(
z
-
x
)
+
t
-
2
(
x
+
y
-
z
)
≥
0. So |
D
|
≥
10
n
/
7.Remark 25.
Forn
≥
3, γ
(
P
6
□
C
n
)
>
γ
(
P
6
)
·
γ
(
C
n
)
=
2
·
⌈
n
/
3
⌉.


## 4. Bounds for General Case

In this section we give rough bounds ofγ
(
P
m
□
C
n
) for any m
,
n
≥
5. If m
=
5
p
+
k and n
=
5
q
+
l, where p
,
q are natural numbers and k
,
l
=
0,1
,
2,3
,
4, a lower bound for γ
(
P
m
□
C
n
) is ⌈
m
n
/
5
⌉
=
5
p
q
+
k
q
+
p
l
+
⌈
k
l
/
5
⌉, as a vertex can dominate at most 5 vertices. An upper bound of γ
(
P
m
□
C
n
) is given by 5
p
q
+
(
k
+
2
)
q
+
(
l
+
1
)
p if l
≠
0 and 5
p
q
+
(
k
+
2
)
q if l
=
0. A dominating set with above cardinality can be constructed as follows.Step 1.
Consider the subsetD
=
{
(
0,0
)
,
(
1,2
)
,
(
2,4
)
,
(
3,1
)
,
(
4,3
)
} of P
5
□
C
n as shown in Figure 9. Modified concatenation columnwise and concatenation rowwise are shown in Figures 9 and 10, respectively.Figure 9
Modified concatenation of subsets of dominating sets columnwise, where□ denotes the vertex not captured by the subset.Figure 10
Concatenation of subsets of dominating sets row wise.Step 2.
Construct a subset ofP
5
p
□
C
5
q using modified concatenation columnwise q many times and using concatenation rowwise p many times the set D as shown in Figure 11.Figure 11
Modified concatenation and concatenation of subsets of dominating sets both column- and row wise.Figure 12
Dominating sets forP
6
□
C
26 and P
6
□
C
27.Figure 13
Dominating sets forP
6
□
C
8 and P
6
□
C
9.Figure 14
Dominating sets forP
6
□
C
10 and P
6
□
C
11.Figure 15
Dominating sets forP
6
□
C
12 and P
6
□
C
13.Figure 16
Dominating sets forP
6
□
C
14, P
6
□
C
15, P
6
□
C
16, and P
6
□
C
17.Figure 17
Dominating sets forP
6
□
C
18, P
6
□
C
19, P
6
□
C
20, P
6
□
C
21, and P
6
□
C
22.Figure 18
Dominating sets forP
6
□
C
23, P
6
□
C
24, and P
6
□
C
25.Step 3.
Add extraq suitably chosen vertices in the first row and extra q suitably chosen vertices in the last row to construct dominating set for P
5
p
□
C
5
q. Hence a dominating set of P
5
p
□
C
5
q is {
(
5
i
,
5
j
)
,
(
5
i
+
1,5
j
+
2
)
,
(
5
i
+
2,5
j
+
4
)
,
(
5
i
+
3,5
j
+
1
)
,
(
5
i
+
4,5
j
+
3
)
:
i
=
0,1
,
…
,
p
-
1
,
j
=
0,1
,
…
,
q
-
1
}
∪
{
(
0,5
j
+
4
)
:
j
=
0,1
,
…
,
q
-
1
}
∪
{
(
5
p
-
1,5
j
)
:
j
=
0,1
,
…
,
q
-
1
}.Step 4.
One can construct a dominating set forP
5
p
+
k
□
C
5
q
+
l, (
k
,
l
)
≠
(
0,0
), using concatenation and modified concatenation between the above dominating set for P
5
p
□
C
5
q and a suitably chosen subset D
′ of vertices for extra k rows and l columns. The cardinality of D
′ will be k
q
+
(
l
+
1
)
p if l
≠
0 and k
q if l
=
0.Remark 26.
We have already seen that ifm
=
5
p
+
k and n
=
5
q
+
l, where p
,
q are natural numbers and k
,
l
=
0,1
,
2,3
,
4, then
(14)
⌈
m
n
5
⌉
=
5
p
q
+
k
q
+
p
l
+
⌈
k
l
5
⌉
≤
γ
(
P
m
□
C
n
)
≤
{
5
p
q
+
(
k
+
2
)
q
+
(
l
+
1
)
p
,
if
l
≠
0
5
p
q
+
(
k
+
2
)
q
,
if
l
=
0
.
Thus we have(15)
1
+
l
5
q
≤
lim
⁡
p
→
∞
γ
(
P
m
C
n
)
5
p
q
≤
1
+
l
+
1
5
q
,
for
l
≠
0
,
lim
⁡
p
→
∞
γ
(
P
m
□
C
n
)
5
p
q
=
1
,
for
l
=
0
.
Therefore,1
+
(
k
/
5
p
)
≤
lim
⁡
q
→
∞
(
γ
(
P
m
□
C
n
)
/
5
p
q
)
≤
1
+
(
(
k
+
2
)
/
5
p
)
,
for
l
=
0 and lim
⁡
p
,
q
→
∞
(
γ
(
P
m
□
C
n
)
/
5
p
q
)
=
1.


## 5. Application of Domination Number in Wireless Sensor Networks

Wireless sensor networks (WSN) provide a new communication and networking paradigms and myriad new applications. The wireless sensors have small size, low battery capacity, nonrenewable power supply, small processing power, limited buffer capacity, and low-power radio. They may measure distance, direction, speed, humidity, wind speed, soil makeup, temperature, chemicals, light and various other parameters. Recent advancements in wireless communications and electronics have enabled the development of low-cost WSN. A WSN usually consists of a large number of small sensor nodes, which are equipped with one or more sensors, some processing circuit and a wireless transceiver. One of the unique features of a WSN is random deployment in inaccessible terrains and cooperative effort that offers unprecedented opportunities for a broad spectrum of civilian and military applications; such as industrial automation, military tactical surveillance and national security [18]. Sensor Networks are useful in detecting topological events such as forest fires [19]. Sensor networks aim at monitoring their surroundings for event detection and object tracking [20]. Because of this surveillance goal,coverage is the functional basis of any sensor network. In order to fulfill its designated surveillance tasks, a sensor network must fully cover the Region of Interest (ROI) without leaving anyinternal sensing hole [21]. The ROI may be a rectangular grid, which may be divided into several squares.In general, a sensor is placed at the center of a square, known as center node as shown in Figure19. This sensor can detect events or tracking objects at the center node along with the four centers of the four adjacent squares which have a common edge with the center square. These four centers are known as Distance-one nodes as shown in Figure 19. The sensor placed at the center node cannot detect events or tracking objects placed at the center of the other squares, for example, Distance-two node as shown in Figure 19. Our objective is to place minimum number of sensors at the center of some selected squares in such a way that they can detect the events or tracking the objects at the center of all the squares. Then the minimum number of sensor required is the same as the domination number of the corresponding rectangular grid and a minimum dominating set will suggest which squares we have to choose.Figure 19
Nodes placed in cells of the ROI.


## 6. Conclusion

In this paper we find the domination numbers of the graphsP
m
□
C
n, m
=
5, n
≥
3. We also provide bounds on γ
(
P
6
□
C
n
), n
≥
3. Minimum dominating sets corresponding to the above-mentioned graphs are also constructed. Moreover, we provide rough bounds on domination numbers of the graphs γ
(
P
m
□
C
n
), m
≥
7 and n
≥
3, and in future, we would like to provide sharper bounds. We also point out how domination numbers and minimum dominating sets may be useful to wireless sensor networks.



---

*Source: 348359-2014-04-07.xml*