# L

Authors: Zehui Shao; Aleksander Vesel
Journal: The Scientific World Journal
 (2014)

---

## Abstract

AnL
(
2,1
)-labeling of a graph G
=
(
V
,
E
) is a function f from the vertex set V
(
G
) to the set of nonnegative integers such that the labels on adjacent vertices differ by at least two and the labels on vertices at distance two differ by at least one. The span of f is the difference between the largest and the smallest numbers in f
(
V
). The λ-number of G, denoted by λ
(
G
), is the minimum span over all L
(
2,1
)-labelings of G. We consider the λ-number of P
n
⊠
C
m and for n
≤
11 the λ-number of C
n
⊠
C
m. We determine λ-numbers of graphs of interest with the exception of a finite number of graphs and we improve the bounds on the λ-number of C
n
⊠
C
m, m
≥
24 and n
≥
26.


---

## Body

## 1. Introduction

The Frequency Assignment Problem (FAP) requires assigning frequencies to transmitters in a wireless network. In a broadcasting network, each transmitter is assigned a frequency channel for its transmissions. Two transmissions can interfere if their channels are too close. That means that even if two transmitters use different channels, there still may be interference if the two transmitters are located close to each other [1, 2].The spectrum of frequencies gets more and more scarce because of increasing demands, both civil and military. Thus the task is to minimize the span of frequencies while avoiding interference. One of the graph-theoretical models of FAP which is well elaborated is the concept of distance-constrained labeling of graphs [1]. Many variants of this concept have been proposed; however, the L
(
2,1
)-labeling problem where adjacent vertices must be assigned colors of distance at least two apart and vertices of distance two must be assigned different colors has attracted the most of interest [3, 4].AnL
(
2,1
)-labeling of a graph G is a function f from the vertex set V
(
G
) to the set of nonnegative integers C (called labels or colors) such that for any two vertices u and v
(1)
|
f
(
u
)
-
f
(
v
)
|
≥
2
if
d
(
u
,
v
)
=
1
,
|
f
(
u
)
-
f
(
v
)
|
≥
1
if
d
(
u
,
v
)
=
2
.Ak
-
L
(
2,1
)-labeling is a L
(
2,1
)-labeling of G such that C
=
{
0
,
…
,
k
}. An optimal L
(
2,1
)-labeling of G is a k
-
L
(
2,1
)-labeling with k smallest possible. The largest label used by an optimal L
(
2,1
)-labeling is called the λ-numberof G and denoted by λ
(
G
).There is a number of studies on the algorithms forL
(
2,1
)-labeling problem [1, 5, 6]. It is known to be NP-hard for general graphs [4]. Even for some relatively simple families of graphs such as planar graphs, bipartite graphs, chordal graphs [5], and graphs of treewidth two [7], the problem is also NP-hard.Product graphs are considered in order to gain global information from the factor graphs [8]. Many interesting wireless networks are based on product graphs with simple factors, such as paths and cycles. In particular, any square grid (resp., torus) is the Cartesian product of two paths (resp., cycles) and any octagonal grid (resp., torus) is the strong product of two paths (resp., cycles) [9]. For the Cartesian product of these factors the λ numbers have been completely determined [10–12], while for the strong and the direct product only partial results have been found [13–15].The paper is organized as follows. In Section2, we give definitions and concepts needed in this paper. We also report on the known results for the λ numbers of the graphs of interest. In Section 3, two main computer search methods applied in the paper are described: the dynamic algorithm and the SAT reduction. Finally, in Section 4, we present the results on the λ-number of P
n
⊠
C
m and the λ-number of C
n
⊠
C
m.


## 2. Preliminaries and Previous Results

For a graphG
=
(
V
,
E
), V
(
G
) and E
(
G
) are the sets of vertices and edges of G, respectively. A directed graph D consists of vertices V
(
D
) together with a set of arcs A
(
D
)
⊆
V
(
D
)
×
V
(
D
). We write G also to stand for the vertex set of the graph G. In this paper, only directed and undirected graphs without multiple edges or loops are considered.Thestrong product of graphs G and H is the graph G
⊠
H with vertex set G
×
H and (
x
1
,
x
2
)
(
y
1
,
y
2
)
∈
E
(
G
⊠
H
) whenever x
1
y
1
∈
E
(
G
) and x
2
=
y
2, or x
2
y
2
∈
E
(
H
) and x
1
=
y
1, or x
1
y
1
∈
E
(
G
) and x
2
y
2
∈
E
(
H
). The strong product is commutative and associative, having the trivial graph as a unit (cf. [8]). The subgraph of G
⊠
H induced by u
×
V
(
H
) is isomorphic to H. It is called an H-fiber and denoted by H
u.Thepath
P
n is the graph whose vertices are 0
,
1
,
…
,
n
-
1 and for which two vertices are adjacent precisely if their difference is ±
1. For an integer n
≥
3, the cycle of length
n is the graph C
n whose vertices are 0
,
1
,
…
,
n
-
1 and whose edges are the pairs i, i
+
1, where the arithmetic is done modulo n. Note that the strong product C
6
⊠
C
13, depicted in Figure 1, can be regarded as a graph composed of six copies of C
13 (denoted by C
13
0
,
…
,
C
13
5) or a graph composed of 13 copies of C
6 (denoted by C
6
0
,
…
,
C
6
12).Figure 1
Strong productC
6
⊠
C
13 with a 12
-
L
(
2,1
)-labeling.Awalk in a directed graph D is a sequence of (not necessarily distinct) vertices v
1,v
2
,
…
,
v
n such that v
i
v
i
+
1
∈
A
(
D
) for 1
,
2
,
…
,
n
-
1. If v
1
=
v
n, we say it is a closed walk.IfP is a path (resp., walk), then its length is its number of edges (resp., arcs).The following simple lemma is well known.Lemma 1.
IfH is a subgraph of G, then λ
(
H
)
≤
λ
(
G
).Letf denote a k-L
(
2,1
)-labeling of C
n
⊠
G. We denote by f
i
,
p the restriction of f to G
i
,
G
i
+
1
,
…
,
G
i
+
p
-
1, i
=
0,1
,
…
,
n
-
1 and p
=
1
,
…
,
n
-
p. Note that G
i is isomorphic to G; that is, G
i is the subgraph of G
⊠
C
n induced by V
(
G
)
×
i. We will also write f
i for f
i
,
1.The following lemma provides an upper bound for theλ-number of the strong product of a graph with a cycle.Lemma 2.
Lett
≥
1 and f be a k
-
L
(
2,1
)-labeling of C
n
⊠
G. If f
0
,
p is a k
-
L
(
2,1
)-labeling of C
p
⊠
G, then λ
(
C
n
+
(
t
-
1
)
p
⊠
G
)
≤
k.Proof.
Letf
′ be a function from V
(
C
n
+
(
t
-
1
)
p
⊠
G
) onto the set {
0,1
,
…
,
k
} and f
i
′ the restriction of f
′ to V
(
G
i
). The function f
′ is defined as follows:
(2)
f
i
′
=
{
f
i
,
i
<
n
f
(
i
-
n
)
mod
⁡
p
i
≥
n
.
It is not difficult to see that f
′ is a k
-
L
(
2,1
)-labeling of C
n
+
(
t
-
1
)
p
⊠
G.Given two integersr and s, let S
(
r
,
s
) denote the set of all nonnegative integer combinations of r and s:
(3)
S
(
r
,
s
)
=
{
α
r
+
β
s
:
α
,
β
∈
Z
+
}
.We will need the result of Sylvester [16].Lemma 3.
Ifr
,
s
>
1 are relatively prime integers, then t
∈
S
(
r
,
s
) for all t
≥
(
s
-
1
)
(
r
-
1
).Some partial results on theλ-number for the strong products of two cycles are given in [15].Theorem 4.
Letm
≥
3. Then
(4)
λ
(
C
3
⊠
C
m
)
=
{
16
,
m
=
3,6
14
,
m
=
5,7
,
10,11,15
13
,
m
=
9,14,18,19,22,23,27,31,35
12
,
o
t
h
e
r
w
i
s
e
.Theorem 5.
Letm
≥
3. Then
(5)
λ
(
C
4
⊠
C
m
)
=
{
19
,
m
=
5
15
,
m
=
4,8
14
,
m
=
11
13
,
m
=
7,10,14,17,20,23
11
,
m
≡
0
(
mod
⁡
6
)
12
,
o
t
h
e
r
w
i
s
e
.Theorem 6.
Ifm
≥
24 and n
≥
36, then λ
(
C
n
⊠
C
m
)
≤
12.For the strong product of more than two cycles the following result presented in [14] is known.Theorem 7.
Ifk
≥
1 and m
0
,
…
,
m
k
-
1 are each multiple of 3
k
+
2, then λ
(
C
m
0
⊠
⋯
⊠
C
m
k
-
1
)
=
3
k
+
1.


## 3. Computer Search

### 3.1. Dynamic Algorithm

The idea is introduced in [10] in a more general framework and later used several times, for example, [13, 15]. In order to make the paper self-contained we first describe its basic definitions and results.We define a digraphD
n
,
k as follows. Its vertices are the k
-
L
(
2,1
)-labelings of C
n
⊠
P
2. Let u
=
u
1
u
2 be a vertex of D
n
,
k. Then u
1 and u
2 represent the k
-
L
(
2,1
)-labeling of C
n
⊠
P
2 restricted to the first and second copies of C
n, respectively.Letu and v be two vertices of D
n
,
k. Then u
v
~ denotes the labeling of C
n
⊠
P
3 obtained by applying u
1
,
u
2, and v
2 to the consecutive copies of C
n. (Note that u
v
~ is not always a k
-
L
(
2,1
)-labeling of C
n
⊠
P
3.) We make an arc from u to v in D
n
,
k if and only if the following two conditions are fulfilled:(i) u
2 equals v
1; (
i
i
) u
v
~ is a k
-
L
(
2,1
)-labeling of C
n
⊠
P
3.Analogously, we define a digraphD
n
,
k
′ with the vertex set composed by k
-
L
(
2,1
)-labelings of P
n
⊠
P
2. In other words, if u
=
u
1
u
2 is a vertex of D
n
,
k
′, then u
1 and u
2 represent the k
-
L
(
2,1
)-labeling of P
n
⊠
P
2 restricted to the first and second copies of P
n, respectively. The set of arcs of D
n
,
k
′ is formed analogously as the set of arcs of D
n
,
k.Figure2(a) shows two vertices of D
6,12 denoted by u and v. We can see that the labeling of the second copy of C
6 in u equals the labeling of the first copy of C
6 in v. Moreover, the labeling of u and the labeling of the second copy of C
6 in v induce a 12
-
L
(
2,1
)-labeling of C
6
⊠
P
3. It follows that A
(
D
6,12
) admits an arc from u to v.Two vertices ofD
6,12 (a) and two vertices of V
6,12
3 with a vertex of D
6,12
2 (b).
(a)
(b)The next theorem follows from the results presented in [10].Theorem 8.
C
i
⊠
C
ℓ (resp., P
i
⊠
C
ℓ) admits a k
-
L
(
2,1
)-labeling if and only if D
i
,
k (resp. D
i
,
k
′) contains a closed directed walk of length ℓ.The dynamic algorithm first generates allk
-
L
(
2,1
)-labelings of C
i
⊠
P
2 which are the vertices of D
i
,
k. Since a main building block C
i
⊠
P
2 is usually relatively small, a simple method, for example, backtracking, can be applied for this step. In the next step, the set of edges of D
i
,
k has to be generated. The procedure for this step is described in [15]. The described algorithm however has the time complexity O
(
n
2
), where n denotes the number of vertices in D
i
,
k. Note that n can be very large even for i and k of a moderate size. Some examples for i and k of interest are |
D
5,14
|
=
114984000, |
D
6,11
|
=
1925760, and |
D
8,11
|
=
1072523264. The complexity of the algorithm does not allow a computation of A
(
D
i
,
k
) in a reasonable time for these cases. We have therefore improved this method as described in the sequel.LetV
i
,
k
3 denote the set of all k-L
(
2,1
)-labelings of C
i
⊠
P
3. If u is an element of V
i
,
k
3, then u
1, u
2, u
3 denote the restriction of u to the first, second, and third copies of C
i in C
i
⊠
P
3; respectively. Note that V
i
,
k
3 contains symmetric labelings of C
i
⊠
P
3, that is, if u
∈
V
i
,
k
3, then v
∈
V
i
,
k
3 exists, such that u
1
=
v
3, u
3
=
v
1, and u
2
=
v
2.We now define the digraphD
i
,
k
2 as follows. Let V
(
D
i
,
k
2
) denote the set of k
-
L
(
2,1
)-labelings of C
i
⊠
P
2 obtained from V
i
,
k
3 in the following way: x
=
x
1
x
2 belongs to V
(
D
i
,
k
2
) if and only if there exist u
,
v
∈
V
i
,
k
3 such that u
1
=
x
1, u
2
=
x
2, and v
3
=
x
1, v
2
=
x
2.Figure2(b) shows two vertices of V
6,12
3 denoted by u and v. We can see that the labelings of the first and the second copies of C
6 in u equal the third and the second copies of C
6 in v, respectively. It follows that V
(
D
6,12
2
) possesses the vertex x comprising these two labelings.Letx
,
y
∈
V
(
D
i
,
k
2
). We make an arc from x
=
x
1
x
2 to y
=
y
1
y
2 if and only if x
2
=
y
1 and x
1
x
2
y
2 belongs to V
i
,
k
3.Note that analogous as above we can improve the method forP
i
⊠
C
ℓ. The graph obtained with this procedure (a subgraph of D
i
,
k
′) will be denoted by D
i
,
k
′
2 in the sequel.For a vertexv of a directed graph D, the number of inward (resp., outward) directed arcs from v in D is called an i
n
d
e
g
r
e
e (resp., o
u
t
d
e
g
r
e
e) and denoted by i
n
d
e
g
D
(
v
) (resp., o
u
t
d
e
g
D
(
v
)).We obtain the main result of this section.Theorem 9.
C
i
⊠
C
ℓ (resp., P
i
⊠
C
ℓ) admits a k
-
L
(
2,1
)-labeling if and only if D
i
,
k
2 (resp., D
i
,
k
′
2) contains a closed directed walk of length ℓ.Proof.
It is easy to see thatV
(
D
i
,
k
2
)
⊆
V
(
D
i
,
k
) and A
(
D
i
,
k
2
)
⊆
A
(
D
i
,
k
). From the definition of V
i
,
k
2 for x
∈
V
(
D
i
,
k
2
) it follows that i
n
d
e
g
D
i
,
k
(
x
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
x
)
>
0.
Suppose now fory
∈
V
(
D
i
,
k
) that i
n
d
e
g
D
i
,
k
(
y
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
y
)
>
0. Since V
i
,
k
3 contains all k
-
L
(
2,1
)-labelings of C
i
⊠
P
3 and o
u
t
d
e
g
D
i
,
k
(
y
)
>
0, there has to be a vertex v
∈
V
i
,
k
3 such that v
1
=
y
1 and v
2
=
y
2. Moreover, since i
n
d
e
g
D
i
,
k
(
y
)
>
0, there has to be a vertex u
∈
V
i
,
k
3 such that u
2
=
y
1 and u
3
=
y
2. It follows that y belongs to V
(
D
i
,
k
2
). We have therefore proven that x
∈
V
(
D
i
,
k
2
) if and only if i
n
d
e
g
D
i
,
k
(
x
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
x
)
>
0.
Analogously as above we can show thatx
y is an arc in D
i
,
k
2 if and only if x
y is an arc in D
i
,
k. In other words, we can show that D
i
,
k
2 is isomorphic to subgraph of D
i
,
k induced by V
i
,
k
2. It follows that D
i
,
k
2 contains a closed directed walk of length ℓ if and only if D
i
,
k contains a closed directed walk of the same size and the proof for D
i
,
k is settled.
Since the proof forD
i
,
k
′
2 is analogous, the proof of the theorem is complete.The algorithm for generating the graphD
i
,
k
2 is depicted in Algorithm 1 (Procedure CREATE GRAPH).Algorithm 1
Procedure  CREATE GRAPH(i
,
k
,
N);
begin
V
i
,
k
3:= set of all k-L
(
2,1
)-labelings of C
n
⊠
P
3;
for all  v
=
v
1
v
2
v
3
∈
V
i
,
k
3
do  Insert v
1
v
2 in V
i
,
k
2;
Sort verticesu
1
u
2 of V
i
,
k
2 with respect to u
1, vertices with the same value of u
1 sort with respect to u
2;
for all  v
=
v
1
v
2
v
3
∈
V
i
,
k
3
do
Findu
=
u
1
u
2 in V
i
,
k
2 such that u
1
=
v
1 and u
2
=
v
2;
Findw
=
w
1
w
2 in V
i
,
k
2 such that w
1
=
v
2 and w
2
=
v
3;
Insertw in N
u;
end.Note that the number of vertices ofD
i
,
k
2 can be much smaller than in D
i
,
k. Some examples for i and k of interest are: |
D
5,14
2
|
=
386345700, |
D
6,11
2
|
=
12336, and |
D
8,11
2
|
=
8157632. However, this reduction is not the only positive effect of the new approach. It is also of a great importance that the running time of CREATE GRAPH is O
(
n
log
⁡
n
), where n, the number of vertices in V
i
,
k
3. In order to see this, note that the running time of an efficient sorting algorithm is also within this time bound. Moreover, this is also the running time of the duration of loop, since a single search in an ordered list with n elements requires O
(
log
⁡
n
) time.The final step of the approach is the search for closed direct walks inD
i
,
k
2. We can find these walks by applying a matrix multiplication of the adjacency matrix of D
i
,
k
2 or a breadth (depth) first search in D
i
,
k
2. Since graphs D
i
,
k
2 are relatively sparse for i and k of interest, the later approach has been applied in order to compute the results of this paper.


### 3.2.  SAT Reduction fork
-
L
(
2,1
)-Labeling

The approach is proposed in [17] for the distance-constrained labeling problem. Here we present this method adapted for L
(
2,1
)-labeling.LetG
=
(
V
,
E
) be a graph and k a positive integer. For every v
∈
V and every i
∈
{
0,1
,
2
,
…
,
k
} introduce an atom x
v
,
i. Intuitively, this atom shows that the vertex v is assigned the color i. Consider the following propositional formulas:(1)
for allv
∈
V, ∨
i
=
0
k
x
v
,
i;
(2)
for allv
∈
V, 0
≤
i
<
j
≤
k, ¬
x
v
,
i
∨
¬
x
v
,
j;
(3)
for allv, u
∈
V, 0
≤
i, j
≤
k with d
(
v
,
u
)
=
1 and |
i
-
j
|
<
2 or d
(
v
,
u
)
=
2 and |
i
-
j
|
<
1, ¬
x
v
,
i
∨
¬
x
u
,
j.Clauses(
1
) and (
2
) ensure that each vertex is labeled with exactly one label. Clause (
3
) guarantees that an obtained labeling is a k
-
L
(
2,1
)-labeling of G. Therefore, the above propositional formulas transform an L
(
2,1
)-labeling problem into a propositional satisfiability test (SAT). We can see that an obtained SAT instance is satisfiable if and only if G admits a k
-
L
(
2,1
)-labeling.


## 3.1. Dynamic Algorithm

The idea is introduced in [10] in a more general framework and later used several times, for example, [13, 15]. In order to make the paper self-contained we first describe its basic definitions and results.We define a digraphD
n
,
k as follows. Its vertices are the k
-
L
(
2,1
)-labelings of C
n
⊠
P
2. Let u
=
u
1
u
2 be a vertex of D
n
,
k. Then u
1 and u
2 represent the k
-
L
(
2,1
)-labeling of C
n
⊠
P
2 restricted to the first and second copies of C
n, respectively.Letu and v be two vertices of D
n
,
k. Then u
v
~ denotes the labeling of C
n
⊠
P
3 obtained by applying u
1
,
u
2, and v
2 to the consecutive copies of C
n. (Note that u
v
~ is not always a k
-
L
(
2,1
)-labeling of C
n
⊠
P
3.) We make an arc from u to v in D
n
,
k if and only if the following two conditions are fulfilled:(i) u
2 equals v
1; (
i
i
) u
v
~ is a k
-
L
(
2,1
)-labeling of C
n
⊠
P
3.Analogously, we define a digraphD
n
,
k
′ with the vertex set composed by k
-
L
(
2,1
)-labelings of P
n
⊠
P
2. In other words, if u
=
u
1
u
2 is a vertex of D
n
,
k
′, then u
1 and u
2 represent the k
-
L
(
2,1
)-labeling of P
n
⊠
P
2 restricted to the first and second copies of P
n, respectively. The set of arcs of D
n
,
k
′ is formed analogously as the set of arcs of D
n
,
k.Figure2(a) shows two vertices of D
6,12 denoted by u and v. We can see that the labeling of the second copy of C
6 in u equals the labeling of the first copy of C
6 in v. Moreover, the labeling of u and the labeling of the second copy of C
6 in v induce a 12
-
L
(
2,1
)-labeling of C
6
⊠
P
3. It follows that A
(
D
6,12
) admits an arc from u to v.Two vertices ofD
6,12 (a) and two vertices of V
6,12
3 with a vertex of D
6,12
2 (b).
(a)
(b)The next theorem follows from the results presented in [10].Theorem 8.
C
i
⊠
C
ℓ (resp., P
i
⊠
C
ℓ) admits a k
-
L
(
2,1
)-labeling if and only if D
i
,
k (resp. D
i
,
k
′) contains a closed directed walk of length ℓ.The dynamic algorithm first generates allk
-
L
(
2,1
)-labelings of C
i
⊠
P
2 which are the vertices of D
i
,
k. Since a main building block C
i
⊠
P
2 is usually relatively small, a simple method, for example, backtracking, can be applied for this step. In the next step, the set of edges of D
i
,
k has to be generated. The procedure for this step is described in [15]. The described algorithm however has the time complexity O
(
n
2
), where n denotes the number of vertices in D
i
,
k. Note that n can be very large even for i and k of a moderate size. Some examples for i and k of interest are |
D
5,14
|
=
114984000, |
D
6,11
|
=
1925760, and |
D
8,11
|
=
1072523264. The complexity of the algorithm does not allow a computation of A
(
D
i
,
k
) in a reasonable time for these cases. We have therefore improved this method as described in the sequel.LetV
i
,
k
3 denote the set of all k-L
(
2,1
)-labelings of C
i
⊠
P
3. If u is an element of V
i
,
k
3, then u
1, u
2, u
3 denote the restriction of u to the first, second, and third copies of C
i in C
i
⊠
P
3; respectively. Note that V
i
,
k
3 contains symmetric labelings of C
i
⊠
P
3, that is, if u
∈
V
i
,
k
3, then v
∈
V
i
,
k
3 exists, such that u
1
=
v
3, u
3
=
v
1, and u
2
=
v
2.We now define the digraphD
i
,
k
2 as follows. Let V
(
D
i
,
k
2
) denote the set of k
-
L
(
2,1
)-labelings of C
i
⊠
P
2 obtained from V
i
,
k
3 in the following way: x
=
x
1
x
2 belongs to V
(
D
i
,
k
2
) if and only if there exist u
,
v
∈
V
i
,
k
3 such that u
1
=
x
1, u
2
=
x
2, and v
3
=
x
1, v
2
=
x
2.Figure2(b) shows two vertices of V
6,12
3 denoted by u and v. We can see that the labelings of the first and the second copies of C
6 in u equal the third and the second copies of C
6 in v, respectively. It follows that V
(
D
6,12
2
) possesses the vertex x comprising these two labelings.Letx
,
y
∈
V
(
D
i
,
k
2
). We make an arc from x
=
x
1
x
2 to y
=
y
1
y
2 if and only if x
2
=
y
1 and x
1
x
2
y
2 belongs to V
i
,
k
3.Note that analogous as above we can improve the method forP
i
⊠
C
ℓ. The graph obtained with this procedure (a subgraph of D
i
,
k
′) will be denoted by D
i
,
k
′
2 in the sequel.For a vertexv of a directed graph D, the number of inward (resp., outward) directed arcs from v in D is called an i
n
d
e
g
r
e
e (resp., o
u
t
d
e
g
r
e
e) and denoted by i
n
d
e
g
D
(
v
) (resp., o
u
t
d
e
g
D
(
v
)).We obtain the main result of this section.Theorem 9.
C
i
⊠
C
ℓ (resp., P
i
⊠
C
ℓ) admits a k
-
L
(
2,1
)-labeling if and only if D
i
,
k
2 (resp., D
i
,
k
′
2) contains a closed directed walk of length ℓ.Proof.
It is easy to see thatV
(
D
i
,
k
2
)
⊆
V
(
D
i
,
k
) and A
(
D
i
,
k
2
)
⊆
A
(
D
i
,
k
). From the definition of V
i
,
k
2 for x
∈
V
(
D
i
,
k
2
) it follows that i
n
d
e
g
D
i
,
k
(
x
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
x
)
>
0.
Suppose now fory
∈
V
(
D
i
,
k
) that i
n
d
e
g
D
i
,
k
(
y
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
y
)
>
0. Since V
i
,
k
3 contains all k
-
L
(
2,1
)-labelings of C
i
⊠
P
3 and o
u
t
d
e
g
D
i
,
k
(
y
)
>
0, there has to be a vertex v
∈
V
i
,
k
3 such that v
1
=
y
1 and v
2
=
y
2. Moreover, since i
n
d
e
g
D
i
,
k
(
y
)
>
0, there has to be a vertex u
∈
V
i
,
k
3 such that u
2
=
y
1 and u
3
=
y
2. It follows that y belongs to V
(
D
i
,
k
2
). We have therefore proven that x
∈
V
(
D
i
,
k
2
) if and only if i
n
d
e
g
D
i
,
k
(
x
)
>
0 and o
u
t
d
e
g
D
i
,
k
(
x
)
>
0.
Analogously as above we can show thatx
y is an arc in D
i
,
k
2 if and only if x
y is an arc in D
i
,
k. In other words, we can show that D
i
,
k
2 is isomorphic to subgraph of D
i
,
k induced by V
i
,
k
2. It follows that D
i
,
k
2 contains a closed directed walk of length ℓ if and only if D
i
,
k contains a closed directed walk of the same size and the proof for D
i
,
k is settled.
Since the proof forD
i
,
k
′
2 is analogous, the proof of the theorem is complete.The algorithm for generating the graphD
i
,
k
2 is depicted in Algorithm 1 (Procedure CREATE GRAPH).Algorithm 1
Procedure  CREATE GRAPH(i
,
k
,
N);
begin
V
i
,
k
3:= set of all k-L
(
2,1
)-labelings of C
n
⊠
P
3;
for all  v
=
v
1
v
2
v
3
∈
V
i
,
k
3
do  Insert v
1
v
2 in V
i
,
k
2;
Sort verticesu
1
u
2 of V
i
,
k
2 with respect to u
1, vertices with the same value of u
1 sort with respect to u
2;
for all  v
=
v
1
v
2
v
3
∈
V
i
,
k
3
do
Findu
=
u
1
u
2 in V
i
,
k
2 such that u
1
=
v
1 and u
2
=
v
2;
Findw
=
w
1
w
2 in V
i
,
k
2 such that w
1
=
v
2 and w
2
=
v
3;
Insertw in N
u;
end.Note that the number of vertices ofD
i
,
k
2 can be much smaller than in D
i
,
k. Some examples for i and k of interest are: |
D
5,14
2
|
=
386345700, |
D
6,11
2
|
=
12336, and |
D
8,11
2
|
=
8157632. However, this reduction is not the only positive effect of the new approach. It is also of a great importance that the running time of CREATE GRAPH is O
(
n
log
⁡
n
), where n, the number of vertices in V
i
,
k
3. In order to see this, note that the running time of an efficient sorting algorithm is also within this time bound. Moreover, this is also the running time of the duration of loop, since a single search in an ordered list with n elements requires O
(
log
⁡
n
) time.The final step of the approach is the search for closed direct walks inD
i
,
k
2. We can find these walks by applying a matrix multiplication of the adjacency matrix of D
i
,
k
2 or a breadth (depth) first search in D
i
,
k
2. Since graphs D
i
,
k
2 are relatively sparse for i and k of interest, the later approach has been applied in order to compute the results of this paper.


## 3.2.  SAT Reduction fork
-
L
(
2,1
)-Labeling

The approach is proposed in [17] for the distance-constrained labeling problem. Here we present this method adapted for L
(
2,1
)-labeling.LetG
=
(
V
,
E
) be a graph and k a positive integer. For every v
∈
V and every i
∈
{
0,1
,
2
,
…
,
k
} introduce an atom x
v
,
i. Intuitively, this atom shows that the vertex v is assigned the color i. Consider the following propositional formulas:(1)
for allv
∈
V, ∨
i
=
0
k
x
v
,
i;
(2)
for allv
∈
V, 0
≤
i
<
j
≤
k, ¬
x
v
,
i
∨
¬
x
v
,
j;
(3)
for allv, u
∈
V, 0
≤
i, j
≤
k with d
(
v
,
u
)
=
1 and |
i
-
j
|
<
2 or d
(
v
,
u
)
=
2 and |
i
-
j
|
<
1, ¬
x
v
,
i
∨
¬
x
u
,
j.Clauses(
1
) and (
2
) ensure that each vertex is labeled with exactly one label. Clause (
3
) guarantees that an obtained labeling is a k
-
L
(
2,1
)-labeling of G. Therefore, the above propositional formulas transform an L
(
2,1
)-labeling problem into a propositional satisfiability test (SAT). We can see that an obtained SAT instance is satisfiable if and only if G admits a k
-
L
(
2,1
)-labeling.


## 4. Results

### 4.1. SAT Reduction

We solve the SAT instances transformed fromL
(
2,1
)-labeling problems described in Section 4.2 by using the software MiniSat [18]. As a result, we have obtained the λ-numbers of P
n
⊠
C
m presented in Table 1 and the λ-numbers of C
n
⊠
C
m presented in Table 2.Table 1
Values ofλ
(
P
n
⊠
C
m
).
n
∖
m
3
4
5
6
7
8
9
10
11
12
3
11
11
14
11
11
11
11
11
10
10
4
11
11
14
11
11
11
11
11
10
11
5
12
11
14
11
11
11
12
12
10
11
6
12
11
14
11
11
11
12
12
10
11
7
12
11
14
11
12
11
12
12
10
11Table 2
Values ofλ
(
C
n
⊠
C
m
).
n
∖
m
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
5
24
a
14
a
17
19
14
16
18
14
16
17
14
15
16
14
15
16
14
15
16
14
15
16
6
1
6
a
1
4
a
11
13
13
13
11
12
13
12
11
12
13
12
11
12
12
12
11
12
12
7
13
13
13
12
12
12
12
13
13
13
13
13
13
12
12
12
12
12
12
12
8
13
12
13
12
11
12
12
12
12
12
11
12
12
12
12
12
11
12
12
9
13
13
/
14
13
12
12
13
13
12
12
13
13
12
12
13
13
12
12
12
10
13
13
12
13
12
13
13
13
12
12
12
12
13
12
12
12
13
11
10
12
12
12
12
12
11
12
12
12
12
10
12
11
12
12
12
11
12
12
12
11
12
11
12
11
12
12
12
11
12
12The values in Table2 marked with a denote the results already obtained in [15], while the entry with 13
/
14 means that the corresponding value is either 13 or 14.


### 4.2.λ-Labeling of C
n
⊠
C
m

Proposition 10.
λ
(
C
5
⊠
C
m
)
=
14 only if m
≡
0
(
mod
⁡
3
).Proof.
Note thatλ
(
C
5
⊠
P
3
)
=
14. We can see that λ
(
C
5
⊠
P
3
)
≤
14 from the fact that every pair of vertices u
,
v
∈
V
(
C
5
⊠
P
3
) is at distance at most two. Let f denote a 14
-
L
(
2,1
)-labeling of C
5
⊠
C
m and f
k its restriction to C
5
k. Let also L
k denote the set of labels used in f
k. Since λ
(
C
5
⊠
P
3
)
=
14, we have |
L
k
|
=
5 and |
L
k
|
+
|
L
k
+
1
|
=
10. Therefore, the restriction of f to C
5
k
+
3 has to comprise the same set of labels as the restriction of f to C
5
k or, more formally, L
k
=
L
k
+
3. It is straightforward to see that this equality can be satisfied in C
5
⊠
C
m only if m
≡
0 (mod 3).Theorem 11.
Letm
≥
5. Then
(6)
λ
(
C
5
⊠
C
m
)
=
{
14
,
m
≡
0
(
mod
⁡
3
)
,
17
,
m
=
7,14
,
19
,
m
=
8
,
18
,
m
=
11
,
16
,
m
=
10,13,17,20,23,26,29
,
15
,
o
t
h
e
r
w
i
s
e
.Proof.
Note that the values form
≤
26 are given in Table 2. We can also show by using the SAT reduction that λ
(
C
5
⊠
C
29
)
=
16. Since λ
(
C
5
⊠
C
j
)
=
14 only if j
≡
0
(
mod
⁡
3
), we construct below a 14
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j, j
≥
1, a 15
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j
+
1, j
≥
5, and a 15
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j
+
2, j
≥
10.
Let[
a
,
b
] for b
≥
a denote the set {
a
,
a
+
1
,
…
,
b
}.
Letf denote a function from V
(
C
5
⊠
C
m
) to [
0,14
] and f
k its restriction to C
5
k, k
≤
m
-
1. Let also L
k denote the set of labels used in f
k. If we set for i
≥
0 and s
∈
{
0,1
,
2
}: L
3
i
+
s
:
=
[
5
s
,
5
s
+
4
], then f is a 14
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j for j
≥
1.
Letf
′ denote a function from V
(
C
5
⊠
C
m
) to [
0,15
] and f
k
′ its restriction to C
5
k, k
≤
m
-
1. Let also L
k
′ denote the set of labels used in f
k
′. If we set for for 0
≤
i
≤
3: L
3
i
′
∶
=
[
15
-
i
,
15
]
∪
[
0,3
-
i
], L
3
i
+
1
′
∶
=
[
4
-
i
,
8
-
i
], L
3
i
+
2
′
∶
=
[
9
-
i
,
13
-
i
] and for i
≥
4 and s
∈
{
0,1
,
2
}: L
3
i
+
s
∶
=
[
5
s
,
5
s
+
4
], then f
′ is a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j
+
1 for j
≥
5. As an example, observe the following pattern representing a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
22:
15
4
9
14
3
8
13
2
7
12
1
6
11
0
5
10
0
5
10
0
5
10
0
5
10
15
4
9
14
3
8
13
2
7
12
1
6
11
1
6
11
1
6
11
1
6
11
0
5
10
15
4
9
14
3
8
13
2
7
12
2
7
12
2
7
12
2
7
12
1
6
11
0
5
10
15
4
9
14
3
8
13
3
8
13
3
8
13
3
8
13
2
7
12
1
6
11
0
5
10
15
4
9
14
4
9
14
4
9
14
Letf
′′ denote a function from V
(
C
5
⊠
C
m
) to [
0,15
] and f
k
′′ its restriction to C
5
k, k
≤
m
-
1. Let also L
k
′′ denote the set of labels used in f
k
′′. If we set for for 0
≤
k
≤
31: L
k
′′
∶
=
L
k
′ and for i
≥
11 and s
∈
{
0,1
,
2
}: L
3
i
+
s
′′
∶
=
[
5
s
,
5
s
+
4
], then f
′′ is a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j
+
2 for j
≥
10. This assertion concludes the proof.The following results partially depend on comprehensive constructions which provide labelings of interest. These constructions are mostly not included in this paper and can be obtained by the authors.Proposition 12.
λ
(
C
6
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
4
).Proof.
The graphD
6,11
2 with 12336 vertices and the largest outdegree six has been computed. Since breadth first search algorithm has found only cycles of length four, Theorem 9 yields the proof.Theorem 13.
Ifm
≥
6, then
(7)
λ
(
C
6
⊠
C
m
)
=
{
11
,
m
≡
0
(
mod
⁡
4
)
16
,
m
=
6
14
,
m
=
7
13
,
m
=
9,10,11,14
12
,
o
t
h
e
r
w
i
s
e
.Proof.
The results form
=
6,7
,
9,10,11,14 follow from Table 2. We can also see in Table 1 that λ
(
C
6
⊠
P
3
)
=
11; thus, from Lemma 1 it follows that λ
(
C
6
⊠
C
m
)
≥
11. Moreover, Proposition 12 says that λ
(
C
6
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
4
). In order to see that λ
(
C
6
⊠
C
m
)
≤
12 for other m of interest, see as an example a 12
-
L
(
2,1
)-labeling of C
6
⊠
C
13 depicted in Figure 1.
From Lemma2 it follows that λ
(
C
6
⊠
C
m
)
≤
12 if m
≡
0
(
mod
⁡
13
). Analogously, we have found 12
-
L
(
2,1
)-labelings of C
6
⊠
C
40, C
6
⊠
C
41, C
6
⊠
C
29, C
6
⊠
C
30, C
6
⊠
C
44, C
6
⊠
C
45, C
6
⊠
C
33, C
6
⊠
C
34, C
6
⊠
C
48, C
6
⊠
C
36, C
6
⊠
C
50, and C
6
⊠
C
38. Any of these labelings restricted to the first 13 copies of C
6 induces a 12
-
L
(
2,1
)-labeling of C
6
⊠
C
13. From Lemma 2 it follows that λ
(
C
6
⊠
C
13
k
+
1
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
2
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
3
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
4
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
5
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
6
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
7
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
8
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
9
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
10
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
11
)
≤
12 for k
≥
3, and λ
(
C
6
⊠
C
13
k
+
12
)
≤
12 for k
≥
2.
Since we have also found12
-
L
(
2,1
)-labelings of C
6
⊠
C
27, C
6
⊠
C
28, C
6
⊠
C
31, C
6
⊠
C
32, C
6
⊠
C
35, and C
6
⊠
C
37, we conclude that λ
(
C
6
⊠
C
m
)
≤
12 for m
≥
27 and the proof is complete.Theorem 14.
Ifm
≥
7, then
(8)
λ
(
C
7
⊠
C
m
)
=
{
13
,
m
=
7,8
,
9,14,15,16,17
,
18,19,27,28,29
12
,
o
t
h
e
r
w
i
s
e
.Proof.
The results form
≤
26 follow from Table 2. We have also established the results for m
=
27,28,29 by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems. Since λ
(
C
7
⊠
P
7
)
=
12 as we can see in Table 2, it follows by Lemma 1 that λ
(
C
7
⊠
C
m
)
≥
12 for m
≥
7. In order to see that λ
(
C
7
⊠
C
m
)
≤
12 for other m of interest, see as an example a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
21 depicted in Figure 3. This labeling restricted to the first ten copies of C
7 induces a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
10. From Lemma 2 it follows that λ
(
C
7
⊠
C
10
k
+
1
)
≤
12, k
≥
2, and λ
(
C
7
⊠
C
10
k
)
≤
12, k
≥
1.
Analogously, we have found12
-
L
(
2,1
)-labelings of C
7
⊠
C
22, C
7
⊠
C
23, C
7
⊠
C
34, C
7
⊠
C
35, C
7
⊠
C
36, C
7
⊠
C
47, C
7
⊠
C
48, and C
7
⊠
C
49. Any of these labelings restricted to the first ten copies of C
7 is a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
10. From Lemma 2 it follows that λ
(
C
7
⊠
C
10
k
+
2
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
3
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
3
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
4
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
5
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
6
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
7
)
≤
12 for k
≥
4, λ
(
C
7
⊠
C
10
k
+
8
)
≤
12 for k
≥
4, and λ
(
C
7
⊠
C
10
k
+
9
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
7
⊠
C
27, C
7
⊠
C
37, C
7
⊠
C
38, and C
7
⊠
C
39, it follows that λ
(
C
7
⊠
C
m
)
≤
12 for all graphs of interest and the proof is complete.Figure 3
12
-
L
(
2,1
)-labeling of C
7
⊠
C
21.Proposition 15.
λ
(
C
8
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
6
).Proof.
The graphD
8,11
2 with 8157632 vertices and the largest outdegree 8 has been computed. Since breadth first search algorithm has found only cycles of length, six, twelve, and twenty-four, Theorem 9 yields the proof.Theorem 16.
Ifm
≥
8, then
(9)
λ
(
C
8
⊠
C
m
)
=
{
11
,
m
≡
0
(
mod
⁡
6
)
13
,
m
=
10
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Sinceλ
(
C
8
⊠
P
7
)
=
11 (see Table 2), it follows from Lemma 1 that λ
(
C
8
⊠
C
m
)
≥
11. Proposition 15 says that λ
(
C
8
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
6
), while the results for m
≤
26 follow from Table 2. Figure 4 shows a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
21. This labeling restricted to the first nine copies of C
8 induces a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
9. From Lemma 2 it follows that λ
(
C
8
⊠
C
9
k
+
3
)
≤
12, k
≥
2, and λ
(
C
8
⊠
C
9
k
)
≤
12, k
≥
1.
Moreover, we have found12
-
L
(
2,1
)-labelings of C
8
⊠
C
46, C
8
⊠
C
47, C
8
⊠
C
40, C
8
⊠
C
50, C
8
⊠
C
24, C
8
⊠
C
43, and C
8
⊠
C
44. Any of these labelings restricted to the first nine copies of C
8 is a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
9. From Lemma 2 it follows that λ
(
C
8
⊠
C
9
k
+
1
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
2
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
4
)
≤
12 for k
≥
4, λ
(
C
8
⊠
C
9
k
+
5
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
6
)
≤
12 for k
≥
2, λ
(
C
8
⊠
C
9
k
+
7
)
≤
12 for k
≥
4, and λ
(
C
8
⊠
C
9
k
+
8
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
8
⊠
C
28, C
8
⊠
C
29, C
8
⊠
C
31, C
8
⊠
C
32, C
8
⊠
C
34, C
8
⊠
C
35, C
8
⊠
C
37, C
8
⊠
C
38, and C
8
⊠
C
41, we establish the desired upper bound for all graphs of interest and the proof is complete.Figure 4
12
-
L
(
2,1
)-labeling of C
8
⊠
C
21.Theorem 17.
Ifm
≥
9, then
(10)
λ
(
C
9
⊠
C
m
)
=
{
13
,
m
=
9,11,15,14,18,19,22,23
13
o
r
14
,
m
=
10
12
o
r
13
,
m
=
27,31,35
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Sinceλ
(
C
9
⊠
P
7
)
=
12 (see Table 2), it follows from Lemma 1 that λ
(
C
9
⊠
C
m
)
≥
12. The results for m
≤
26 follow from Table 2. We have also established by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems that λ
(
C
9
⊠
C
10
) is either 13 or 14, while for m
=
27,31,35 the value of λ
(
C
9
⊠
C
m
) is either 12 or 13. Figure 5 shows a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
28. This labeling restricted to first 12 copies of C
9 induces a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
12. From Lemma 2 it follows that λ
(
C
9
⊠
C
12
k
+
4
)
≤
12, k
≥
2, and λ
(
C
9
⊠
C
12
k
)
≤
12, k
≥
1.
We have also found12
-
L
(
2,1
)-labelings of C
9
⊠
C
49, C
9
⊠
C
50, C
9
⊠
C
63, C
9
⊠
C
29, C
9
⊠
C
66, C
9
⊠
C
55, C
9
⊠
C
32, C
9
⊠
C
33, C
9
⊠
C
58, and C
9
⊠
C
59. Any of these labelings restricted to first 12 copies of C
9 induces a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
12. From Lemma 2 it follows that λ
(
C
9
⊠
C
12
k
+
1
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
2
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
3
)
≤
12 for k
≥
5, λ
(
C
9
⊠
C
12
k
+
5
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
6
)
≤
12 for k
≥
5, λ
(
C
9
⊠
C
12
k
+
7
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
8
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
9
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
10
)
≤
12 for k
≥
4, and λ
(
C
9
⊠
C
12
k
+
11
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
9
⊠
C
30, C
9
⊠
C
34, C
9
⊠
C
37, C
9
⊠
C
38, C
9
⊠
C
39, C
9
⊠
C
42, C
9
⊠
C
43, C
9
⊠
C
46, C
9
⊠
C
47, C
9
⊠
C
51, and C
9
⊠
C
54, we establish that λ
(
C
9
⊠
C
m
)
≤
12 for all m of interest and the proof is complete.Figure 5
12
-
L
(
2,1
)-labeling of C
9
⊠
C
28.Theorem 18.
Ifm
≥
10, then
(11)
λ
(
C
10
⊠
C
m
)
=
{
13
,
m
=
10,11,13,15,16,17,22,26
12
o
r
13
,
27
≤
m
≤
395
12
,
o
t
h
e
r
w
i
s
e
.Proof.
We can see in Table2 that λ
(
C
10
⊠
P
5
)
=
12 hence, it follows by Lemma 1 that λ
(
C
10
⊠
C
m
)
≥
12. The results for m
≤
26 are given in Table 2.
The following pattern represents a12
-
L
(
2,1
)-labeling of C
10
⊠
C
37, while the leftmost 12 columns of the pattern represents a 12
-
L
(
2,1
)-labeling of C
10
⊠
C
12:
8
3
1
12
8
5
7
2
0
11
9
6
8
3
1
12
10
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
3
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
12
10
5
7
4
0
11
9
4
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
6
8
3
1
12
8
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
6
8
3
1
12
10
5
7
4
2
0
11
9
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
10
5
7
4
0
11
9
4
8
3
1
12
10
5
7
4
2
0
11
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
By Lemma2, we have λ
(
C
10
⊠
C
12
α
+
37
β
)
≤
12 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
C
10
⊠
C
m
)
≤
12 for m
≥
(
37
-
1
)
·
(
12
-
1
)
=
396.
We have found13
-
L
(
2,1
)-labelings of C
10
⊠
C
m for 27
≤
m
≤
46 and we can construct 13
-
L
(
2,1
)-labelings of C
10
⊠
C
m for m
≥
36 as follows. We have found 13
-
L
(
2,1
)-labelings of C
10
⊠
C
25, C
10
⊠
C
50, C
10
⊠
C
27, C
10
⊠
C
28, C
10
⊠
C
29, C
10
⊠
C
54, and C
10
⊠
C
39. Any of these labelings restricted to the first eight copies of C
10 is a 13
-
L
(
2,1
)-labeling of C
10
⊠
C
8. From Lemma 2 it follows that λ
(
C
10
⊠
C
8
k
)
≤
13 for k
≥
1, λ
(
C
10
⊠
C
8
k
+
1
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
2
)
≤
13 for k
≥
6, λ
(
C
10
⊠
C
8
k
+
3
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
4
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
5
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
6
)
≤
13 for k
≥
6, and λ
(
C
10
⊠
C
8
k
+
7
)
≤
13 for k
≥
4. These observations complete the proof.Proposition 19.
λ
(
C
11
⊠
C
m
)
=
10 only if m
≡
0
(
mod
⁡
11
).Proof.
The graphD
11,10
2 with 380 vertices and the largest outdegree 2 has been computed. Since breadth first search algorithm has found only cycles of length length 11, Theorem 9 yields the proof.Theorem 20.
Ifm
≥
11, then
(12)
λ
(
C
11
⊠
C
m
)
=
{
10
,
m
≡
0
(
mod
⁡
11
)
12
,
m
∈
{
12,13,14,15,16,18,19
,

20,21,22,23,25,26
}
11
m
≥
270
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
∈
{
12,13,14,15,16,18,19,20,21,22,23,25,26
} the λ numbers are obtained by using the SAT reduction as depicted in Table 1. Since λ
(
C
11
⊠
P
3
)
=
10, from Lemma 1 it follows that λ
(
C
11
⊠
C
m
)
≥
10, while from Proposition 19 it follows that λ
(
C
11
⊠
C
m
)
≥
11 if m
≢
0 (mod 11).
The result form
≡
0
(
mod
⁡
11
) can be obtained by the fact that λ
(
C
11
⊠
C
11
)
=
10 and by Lemma 2.
Figure6 represents an 11
-
L
(
2,1
)-labeling of C
11
⊠
C
28, where the leftmost 11 columns of the figure represent an 11
-
L
(
2,1
)-labeling of C
11
⊠
C
11. By Lemma 2, we have λ
(
C
11
⊠
C
11
α
+
28
β
)
≤
11 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
C
11
⊠
C
m
)
≤
11 for m
≥
(
28
-
1
)
·
(
11
-
1
)
=
270.
In order to find the general upper bound, we present the constructions showing thatλ
(
C
11
⊠
C
m
)
≤
12 for m
≥
26. In particular, Figure 7 shows a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
37. This labeling restricted to the first 12 copies of C
11 induces a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
12. From Lemma 2 it follows that λ
(
C
11
⊠
C
12
k
+
1
)
≤
12, k
≥
3, and λ
(
C
11
⊠
C
12
k
)
≤
12, k
≥
1.
Analogously, we have found12
-
L
(
2,1
)-labelings of C
11
⊠
C
38, C
11
⊠
C
39, C
11
⊠
C
40, C
11
⊠
C
41, C
11
⊠
C
42, C
11
⊠
C
43, C
11
⊠
C
44, C
11
⊠
C
45, C
11
⊠
C
46, and C
11
⊠
C
35. Any of these labelings restricted to the first 12 copies of C
11 is a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
12.
From Lemma2 it follows that λ
(
C
11
⊠
C
12
k
+
2
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
3
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
4
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
5
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
6
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
7
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
8
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
9
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
10
)
≤
12 for k
≥
3, and λ
(
C
11
⊠
C
12
k
+
11
)
≤
12 for k
≥
2.
Since we have also found12
-
L
(
2,1
)-labelings of C
11
⊠
C
27, C
11
⊠
C
28, C
11
⊠
C
29, C
11
⊠
C
30, C
11
⊠
C
31, C
11
⊠
C
32, C
11
⊠
C
33, and C
11
⊠
C
34, we establish that λ
(
C
11
⊠
C
m
)
≤
12 for all m
≥
27 and the proof is complete.Figure 6
11
-
L
(
2,1
)-labeling of C
11
⊠
C
28.Figure 7
12
-
L
(
2,1
)-labeling of C
11
⊠
C
37.


### 4.3.λ-Numbers of P
n
⊠
C
m

Proposition 21.
Ifm
≥
3, then
(13)
λ
(
P
3
⊠
C
m
)
=
{
14
,
m
=
5
11
,
m
∈
{
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}
10
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results are obtained by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems (see Table 1).
The graphD
3,10
′
2 with 9080 vertices and the largest outdegree 16 has been created in order to find 10
-
L
(
2,1
)-labelings in P
3
⊠
C
m. Matrix multiplication has been applied in order to find closed directed walks in the graph. The algorithm has found no closed directed walk of length from the set {
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}
∪
{
5
}. It follows that λ
(
P
3
⊠
C
n
)
≥
11 for any m
∈
{
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}. The upper bounds for m
∈
{
13,14,18,19
} follow from the labelings depicted in Figure 8.
We have found10
-
L
(
2,1
)-labelings of P
3
⊠
C
23, P
3
⊠
C
35, P
3
⊠
C
47, P
3
⊠
C
26, P
3
⊠
C
38, P
3
⊠
C
39, P
3
⊠
C
40, P
3
⊠
C
41, P
3
⊠
C
31, and P
3
⊠
C
43. Any of these labelings restricted to the first 11 copies of P
3 is a 10
-
L
(
2,1
)-labeling of P
3
⊠
C
11. From Lemma 2 it follows that λ
(
P
3
⊠
C
11
k
)
≤
10 for k
≥
1, λ
(
P
3
⊠
C
11
k
+
1
)
≤
10 for k
≥
2, λ
(
P
3
⊠
C
11
k
+
2
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
3
)
≤
10 for k
≥
4, λ
(
P
3
⊠
C
11
k
+
4
)
≤
10 for k
≥
2, λ
(
P
3
⊠
C
11
k
+
5
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
6
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
7
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
8
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
9
)
≤
10 for k
≥
2, and λ
(
P
3
⊠
C
11
k
+
10
)
≤
10 for k
≥
3.
Since we have also found10
-
L
(
2,1
)-labelings of P
3
⊠
C
13, P
3
⊠
C
14, P
3
⊠
C
15, P
3
⊠
C
16, P
3
⊠
C
17, P
3
⊠
C
18, P
3
⊠
C
19, P
3
⊠
C
20, P
3
⊠
C
21, P
3
⊠
C
24, P
3
⊠
C
25, P
3
⊠
C
27, P
3
⊠
C
28, P
3
⊠
C
29, P
3
⊠
C
30, P
3
⊠
C
32, and P
3
⊠
C
36, we establish that λ
(
P
3
⊠
C
m
)
≤
10 for all m
≥
13 and the proof is complete.(a)11
-
L
(
2,1
)-labeling of P
3
⊠
C
3, (b) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
4, (c) 14
-
L
(
2,1
)-labeling of P
3
⊠
C
5, (d) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
7, (e) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
13, and (f) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
19.
(a)
(b)
(c)
(d)
(e)
(f)Proposition 22.
Ifm
≥
3, then
(14)
λ
(
P
4
⊠
C
m
)
=
{
14
,
m
=
5
10
,
m
≡
0
(
mod
⁡
11
)
11
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
=
5 the result is obtained by solving the SAT instance transformed from the corresponding L
(
2,1
)-labeling problem. For m
≡
0
(
mod
⁡
11
) the result follows from Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
In order to find10
-
L
(
2,1
)-labelings in P
4
⊠
C
m, the graph D
4,10
′
2 with 16792 vertices and the largest outdegree 3 has been created. Since breadth first search algorithm has found only cycles of length 11, the upper bound follows.
For allm
≢
0
(
mod
⁡
11
) and m
≥
13 we can construct 11
-
L
(
2,1
)-labelings of P
4
⊠
C
m as described below. We have found 11
-
L
(
2,1
)-labelings of P
4
⊠
C
13, P
4
⊠
C
14, P
4
⊠
C
15, P
4
⊠
C
16, and P
4
⊠
C
17. Any of these labelings restricted to the first six copies of P
4 is an 11
-
L
(
2,1
)-labeling of P
4
⊠
C
11. From Lemma 2 it follows that λ
(
P
4
⊠
C
6
k
+
1
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
2
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
3
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
4
)
≤
11 for k
≥
2, and λ
(
P
4
⊠
C
6
k
+
5
)
≤
11 for k
≥
2. These conclusions complete the proof.Corollary 23.
Letn
,
m
≥
4.(i)
Ifm
≢
0
(
mod
⁡
11
), then
λ
(
P
n
⊠
C
m
)
≥
11,
(ii)
Ifn
≢
0
(
mod
⁡
11
)  or
m
≢
0
(
mod
⁡
11
), then
λ
(
C
n
⊠
C
m
)
≥
11.From Theorem6 now we have the followingCorollary 24.
Ifm
≥
24 and n
≥
26, then
(15)
λ
(
C
n
⊠
C
m
)
=
{
10
,
n
≡
0
(
mod
⁡
11
)

m
≡
0
(
mod
⁡
11
)
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proposition 25.
Ifm
≥
3, then
(16)
λ
(
P
5
⊠
C
m
)
=
{
14
,
m
=
5
12
,
m
=
3,9
,
10
10
,
m
≡
0
(
mod
⁡
11
)
11
,
m
=
4,6
,
7,8
,
12
o
r
m
≥
80
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results follow from Table 1. For m
≡
0
(
mod
⁡
11
) the result follows from Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
Figure9 represents an 11
-
L
(
2,1
)-labeling of P
5
⊠
C
17, where the leftmost six columns of the figure represent an 11
-
L
(
2,1
)-labeling of P
5
⊠
C
6.
By Lemma2, we have λ
(
P
5
⊠
C
6
α
+
17
β
)
≤
11 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
P
5
⊠
C
m
)
≤
11 for m
≥
(
17
-
1
)
·
(
6
-
1
)
=
80.
In order to complete the proof note that from Theorem16 and Lemma 1 it follows that λ
(
P
5
⊠
C
m
)
≤
12 for m
≥
11.Figure 9
11
-
L
(
2,1
)-labeling of P
5
⊠
C
17.Proposition 26.
Ifm
≥
3, then
(17)
λ
(
P
6
⊠
C
m
)
=
{
14
,
m
=
5
12
,
m
=
3,9
,
10
10
,
m
≡
0
(
mod
⁡
11
)
11
,
m
=
4,6
,
7,8
,
12
o
r
m
≥
154
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results follow from Table 1. For m
≡
0
(
mod
⁡
11
) the result follows Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
Figure10 represents a 11
-
L
(
2,1
)-labeling of P
6
⊠
C
23, where the leftmost eight columns of the figure represent an 11
-
L
(
2,1
)-labeling of P
6
⊠
C
8.
By Lemma2, we have λ
(
P
6
⊠
C
8
α
+
23
β
)
≤
11 for integers α and β. From Lemma 3 it follows that λ
(
P
6
⊠
C
m
)
≤
11 for m
≥
(
23
-
1
)
·
(
8
-
1
)
=
154.
We complete the proof by noting that from Theorem16 and Lemma 1 it follows λ
(
P
6
⊠
C
m
)
≤
12 for m
≥
11.Figure 10
11
-
L
(
2,1
)-labeling of P
6
⊠
C
23.Values in Table1, the results from Section 4.2, Theorems 6 and 20, and Corollary 23 provide lower and upper bounds for the λ-number of P
n
⊠
C
m. The results are summarized in the following.Theorem 27.
Ifn
≥
7, then
(18)
λ
(
P
n
⊠
C
m
)
=
{
10
,
m
≡
0
(
mod
⁡
11
)
14
,
m
=
5
12
,
m
=
3,7
,
9,10
11
,
m
=
4,6
,
8,12
o
r
m
≥
270
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.


## 4.1. SAT Reduction

We solve the SAT instances transformed fromL
(
2,1
)-labeling problems described in Section 4.2 by using the software MiniSat [18]. As a result, we have obtained the λ-numbers of P
n
⊠
C
m presented in Table 1 and the λ-numbers of C
n
⊠
C
m presented in Table 2.Table 1
Values ofλ
(
P
n
⊠
C
m
).
n
∖
m
3
4
5
6
7
8
9
10
11
12
3
11
11
14
11
11
11
11
11
10
10
4
11
11
14
11
11
11
11
11
10
11
5
12
11
14
11
11
11
12
12
10
11
6
12
11
14
11
11
11
12
12
10
11
7
12
11
14
11
12
11
12
12
10
11Table 2
Values ofλ
(
C
n
⊠
C
m
).
n
∖
m
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
5
24
a
14
a
17
19
14
16
18
14
16
17
14
15
16
14
15
16
14
15
16
14
15
16
6
1
6
a
1
4
a
11
13
13
13
11
12
13
12
11
12
13
12
11
12
12
12
11
12
12
7
13
13
13
12
12
12
12
13
13
13
13
13
13
12
12
12
12
12
12
12
8
13
12
13
12
11
12
12
12
12
12
11
12
12
12
12
12
11
12
12
9
13
13
/
14
13
12
12
13
13
12
12
13
13
12
12
13
13
12
12
12
10
13
13
12
13
12
13
13
13
12
12
12
12
13
12
12
12
13
11
10
12
12
12
12
12
11
12
12
12
12
10
12
11
12
12
12
11
12
12
12
11
12
11
12
11
12
12
12
11
12
12The values in Table2 marked with a denote the results already obtained in [15], while the entry with 13
/
14 means that the corresponding value is either 13 or 14.


## 4.2.λ-Labeling of C
n
⊠
C
m

Proposition 10.
λ
(
C
5
⊠
C
m
)
=
14 only if m
≡
0
(
mod
⁡
3
).Proof.
Note thatλ
(
C
5
⊠
P
3
)
=
14. We can see that λ
(
C
5
⊠
P
3
)
≤
14 from the fact that every pair of vertices u
,
v
∈
V
(
C
5
⊠
P
3
) is at distance at most two. Let f denote a 14
-
L
(
2,1
)-labeling of C
5
⊠
C
m and f
k its restriction to C
5
k. Let also L
k denote the set of labels used in f
k. Since λ
(
C
5
⊠
P
3
)
=
14, we have |
L
k
|
=
5 and |
L
k
|
+
|
L
k
+
1
|
=
10. Therefore, the restriction of f to C
5
k
+
3 has to comprise the same set of labels as the restriction of f to C
5
k or, more formally, L
k
=
L
k
+
3. It is straightforward to see that this equality can be satisfied in C
5
⊠
C
m only if m
≡
0 (mod 3).Theorem 11.
Letm
≥
5. Then
(6)
λ
(
C
5
⊠
C
m
)
=
{
14
,
m
≡
0
(
mod
⁡
3
)
,
17
,
m
=
7,14
,
19
,
m
=
8
,
18
,
m
=
11
,
16
,
m
=
10,13,17,20,23,26,29
,
15
,
o
t
h
e
r
w
i
s
e
.Proof.
Note that the values form
≤
26 are given in Table 2. We can also show by using the SAT reduction that λ
(
C
5
⊠
C
29
)
=
16. Since λ
(
C
5
⊠
C
j
)
=
14 only if j
≡
0
(
mod
⁡
3
), we construct below a 14
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j, j
≥
1, a 15
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j
+
1, j
≥
5, and a 15
-
L
(
2,1
)-labeling for C
5
⊠
C
3
j
+
2, j
≥
10.
Let[
a
,
b
] for b
≥
a denote the set {
a
,
a
+
1
,
…
,
b
}.
Letf denote a function from V
(
C
5
⊠
C
m
) to [
0,14
] and f
k its restriction to C
5
k, k
≤
m
-
1. Let also L
k denote the set of labels used in f
k. If we set for i
≥
0 and s
∈
{
0,1
,
2
}: L
3
i
+
s
:
=
[
5
s
,
5
s
+
4
], then f is a 14
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j for j
≥
1.
Letf
′ denote a function from V
(
C
5
⊠
C
m
) to [
0,15
] and f
k
′ its restriction to C
5
k, k
≤
m
-
1. Let also L
k
′ denote the set of labels used in f
k
′. If we set for for 0
≤
i
≤
3: L
3
i
′
∶
=
[
15
-
i
,
15
]
∪
[
0,3
-
i
], L
3
i
+
1
′
∶
=
[
4
-
i
,
8
-
i
], L
3
i
+
2
′
∶
=
[
9
-
i
,
13
-
i
] and for i
≥
4 and s
∈
{
0,1
,
2
}: L
3
i
+
s
∶
=
[
5
s
,
5
s
+
4
], then f
′ is a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j
+
1 for j
≥
5. As an example, observe the following pattern representing a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
22:
15
4
9
14
3
8
13
2
7
12
1
6
11
0
5
10
0
5
10
0
5
10
0
5
10
15
4
9
14
3
8
13
2
7
12
1
6
11
1
6
11
1
6
11
1
6
11
0
5
10
15
4
9
14
3
8
13
2
7
12
2
7
12
2
7
12
2
7
12
1
6
11
0
5
10
15
4
9
14
3
8
13
3
8
13
3
8
13
3
8
13
2
7
12
1
6
11
0
5
10
15
4
9
14
4
9
14
4
9
14
Letf
′′ denote a function from V
(
C
5
⊠
C
m
) to [
0,15
] and f
k
′′ its restriction to C
5
k, k
≤
m
-
1. Let also L
k
′′ denote the set of labels used in f
k
′′. If we set for for 0
≤
k
≤
31: L
k
′′
∶
=
L
k
′ and for i
≥
11 and s
∈
{
0,1
,
2
}: L
3
i
+
s
′′
∶
=
[
5
s
,
5
s
+
4
], then f
′′ is a 15
-
L
(
2,1
)-labeling of C
5
⊠
C
3
j
+
2 for j
≥
10. This assertion concludes the proof.The following results partially depend on comprehensive constructions which provide labelings of interest. These constructions are mostly not included in this paper and can be obtained by the authors.Proposition 12.
λ
(
C
6
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
4
).Proof.
The graphD
6,11
2 with 12336 vertices and the largest outdegree six has been computed. Since breadth first search algorithm has found only cycles of length four, Theorem 9 yields the proof.Theorem 13.
Ifm
≥
6, then
(7)
λ
(
C
6
⊠
C
m
)
=
{
11
,
m
≡
0
(
mod
⁡
4
)
16
,
m
=
6
14
,
m
=
7
13
,
m
=
9,10,11,14
12
,
o
t
h
e
r
w
i
s
e
.Proof.
The results form
=
6,7
,
9,10,11,14 follow from Table 2. We can also see in Table 1 that λ
(
C
6
⊠
P
3
)
=
11; thus, from Lemma 1 it follows that λ
(
C
6
⊠
C
m
)
≥
11. Moreover, Proposition 12 says that λ
(
C
6
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
4
). In order to see that λ
(
C
6
⊠
C
m
)
≤
12 for other m of interest, see as an example a 12
-
L
(
2,1
)-labeling of C
6
⊠
C
13 depicted in Figure 1.
From Lemma2 it follows that λ
(
C
6
⊠
C
m
)
≤
12 if m
≡
0
(
mod
⁡
13
). Analogously, we have found 12
-
L
(
2,1
)-labelings of C
6
⊠
C
40, C
6
⊠
C
41, C
6
⊠
C
29, C
6
⊠
C
30, C
6
⊠
C
44, C
6
⊠
C
45, C
6
⊠
C
33, C
6
⊠
C
34, C
6
⊠
C
48, C
6
⊠
C
36, C
6
⊠
C
50, and C
6
⊠
C
38. Any of these labelings restricted to the first 13 copies of C
6 induces a 12
-
L
(
2,1
)-labeling of C
6
⊠
C
13. From Lemma 2 it follows that λ
(
C
6
⊠
C
13
k
+
1
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
2
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
3
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
4
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
5
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
6
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
7
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
8
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
9
)
≤
12 for k
≥
3, λ
(
C
6
⊠
C
13
k
+
10
)
≤
12 for k
≥
2, λ
(
C
6
⊠
C
13
k
+
11
)
≤
12 for k
≥
3, and λ
(
C
6
⊠
C
13
k
+
12
)
≤
12 for k
≥
2.
Since we have also found12
-
L
(
2,1
)-labelings of C
6
⊠
C
27, C
6
⊠
C
28, C
6
⊠
C
31, C
6
⊠
C
32, C
6
⊠
C
35, and C
6
⊠
C
37, we conclude that λ
(
C
6
⊠
C
m
)
≤
12 for m
≥
27 and the proof is complete.Theorem 14.
Ifm
≥
7, then
(8)
λ
(
C
7
⊠
C
m
)
=
{
13
,
m
=
7,8
,
9,14,15,16,17
,
18,19,27,28,29
12
,
o
t
h
e
r
w
i
s
e
.Proof.
The results form
≤
26 follow from Table 2. We have also established the results for m
=
27,28,29 by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems. Since λ
(
C
7
⊠
P
7
)
=
12 as we can see in Table 2, it follows by Lemma 1 that λ
(
C
7
⊠
C
m
)
≥
12 for m
≥
7. In order to see that λ
(
C
7
⊠
C
m
)
≤
12 for other m of interest, see as an example a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
21 depicted in Figure 3. This labeling restricted to the first ten copies of C
7 induces a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
10. From Lemma 2 it follows that λ
(
C
7
⊠
C
10
k
+
1
)
≤
12, k
≥
2, and λ
(
C
7
⊠
C
10
k
)
≤
12, k
≥
1.
Analogously, we have found12
-
L
(
2,1
)-labelings of C
7
⊠
C
22, C
7
⊠
C
23, C
7
⊠
C
34, C
7
⊠
C
35, C
7
⊠
C
36, C
7
⊠
C
47, C
7
⊠
C
48, and C
7
⊠
C
49. Any of these labelings restricted to the first ten copies of C
7 is a 12
-
L
(
2,1
)-labeling of C
7
⊠
C
10. From Lemma 2 it follows that λ
(
C
7
⊠
C
10
k
+
2
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
3
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
3
)
≤
12 for k
≥
2, λ
(
C
7
⊠
C
10
k
+
4
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
5
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
6
)
≤
12 for k
≥
3, λ
(
C
7
⊠
C
10
k
+
7
)
≤
12 for k
≥
4, λ
(
C
7
⊠
C
10
k
+
8
)
≤
12 for k
≥
4, and λ
(
C
7
⊠
C
10
k
+
9
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
7
⊠
C
27, C
7
⊠
C
37, C
7
⊠
C
38, and C
7
⊠
C
39, it follows that λ
(
C
7
⊠
C
m
)
≤
12 for all graphs of interest and the proof is complete.Figure 3
12
-
L
(
2,1
)-labeling of C
7
⊠
C
21.Proposition 15.
λ
(
C
8
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
6
).Proof.
The graphD
8,11
2 with 8157632 vertices and the largest outdegree 8 has been computed. Since breadth first search algorithm has found only cycles of length, six, twelve, and twenty-four, Theorem 9 yields the proof.Theorem 16.
Ifm
≥
8, then
(9)
λ
(
C
8
⊠
C
m
)
=
{
11
,
m
≡
0
(
mod
⁡
6
)
13
,
m
=
10
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Sinceλ
(
C
8
⊠
P
7
)
=
11 (see Table 2), it follows from Lemma 1 that λ
(
C
8
⊠
C
m
)
≥
11. Proposition 15 says that λ
(
C
8
⊠
C
m
)
=
11 only if m
≡
0
(
mod
⁡
6
), while the results for m
≤
26 follow from Table 2. Figure 4 shows a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
21. This labeling restricted to the first nine copies of C
8 induces a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
9. From Lemma 2 it follows that λ
(
C
8
⊠
C
9
k
+
3
)
≤
12, k
≥
2, and λ
(
C
8
⊠
C
9
k
)
≤
12, k
≥
1.
Moreover, we have found12
-
L
(
2,1
)-labelings of C
8
⊠
C
46, C
8
⊠
C
47, C
8
⊠
C
40, C
8
⊠
C
50, C
8
⊠
C
24, C
8
⊠
C
43, and C
8
⊠
C
44. Any of these labelings restricted to the first nine copies of C
8 is a 12
-
L
(
2,1
)-labeling of C
8
⊠
C
9. From Lemma 2 it follows that λ
(
C
8
⊠
C
9
k
+
1
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
2
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
4
)
≤
12 for k
≥
4, λ
(
C
8
⊠
C
9
k
+
5
)
≤
12 for k
≥
5, λ
(
C
8
⊠
C
9
k
+
6
)
≤
12 for k
≥
2, λ
(
C
8
⊠
C
9
k
+
7
)
≤
12 for k
≥
4, and λ
(
C
8
⊠
C
9
k
+
8
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
8
⊠
C
28, C
8
⊠
C
29, C
8
⊠
C
31, C
8
⊠
C
32, C
8
⊠
C
34, C
8
⊠
C
35, C
8
⊠
C
37, C
8
⊠
C
38, and C
8
⊠
C
41, we establish the desired upper bound for all graphs of interest and the proof is complete.Figure 4
12
-
L
(
2,1
)-labeling of C
8
⊠
C
21.Theorem 17.
Ifm
≥
9, then
(10)
λ
(
C
9
⊠
C
m
)
=
{
13
,
m
=
9,11,15,14,18,19,22,23
13
o
r
14
,
m
=
10
12
o
r
13
,
m
=
27,31,35
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Sinceλ
(
C
9
⊠
P
7
)
=
12 (see Table 2), it follows from Lemma 1 that λ
(
C
9
⊠
C
m
)
≥
12. The results for m
≤
26 follow from Table 2. We have also established by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems that λ
(
C
9
⊠
C
10
) is either 13 or 14, while for m
=
27,31,35 the value of λ
(
C
9
⊠
C
m
) is either 12 or 13. Figure 5 shows a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
28. This labeling restricted to first 12 copies of C
9 induces a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
12. From Lemma 2 it follows that λ
(
C
9
⊠
C
12
k
+
4
)
≤
12, k
≥
2, and λ
(
C
9
⊠
C
12
k
)
≤
12, k
≥
1.
We have also found12
-
L
(
2,1
)-labelings of C
9
⊠
C
49, C
9
⊠
C
50, C
9
⊠
C
63, C
9
⊠
C
29, C
9
⊠
C
66, C
9
⊠
C
55, C
9
⊠
C
32, C
9
⊠
C
33, C
9
⊠
C
58, and C
9
⊠
C
59. Any of these labelings restricted to first 12 copies of C
9 induces a 12
-
L
(
2,1
)-labeling of C
9
⊠
C
12. From Lemma 2 it follows that λ
(
C
9
⊠
C
12
k
+
1
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
2
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
3
)
≤
12 for k
≥
5, λ
(
C
9
⊠
C
12
k
+
5
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
6
)
≤
12 for k
≥
5, λ
(
C
9
⊠
C
12
k
+
7
)
≤
12 for k
≥
4, λ
(
C
9
⊠
C
12
k
+
8
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
9
)
≤
12 for k
≥
2, λ
(
C
9
⊠
C
12
k
+
10
)
≤
12 for k
≥
4, and λ
(
C
9
⊠
C
12
k
+
11
)
≤
12 for k
≥
4.
Since we have also found12
-
L
(
2,1
)-labelings of C
9
⊠
C
30, C
9
⊠
C
34, C
9
⊠
C
37, C
9
⊠
C
38, C
9
⊠
C
39, C
9
⊠
C
42, C
9
⊠
C
43, C
9
⊠
C
46, C
9
⊠
C
47, C
9
⊠
C
51, and C
9
⊠
C
54, we establish that λ
(
C
9
⊠
C
m
)
≤
12 for all m of interest and the proof is complete.Figure 5
12
-
L
(
2,1
)-labeling of C
9
⊠
C
28.Theorem 18.
Ifm
≥
10, then
(11)
λ
(
C
10
⊠
C
m
)
=
{
13
,
m
=
10,11,13,15,16,17,22,26
12
o
r
13
,
27
≤
m
≤
395
12
,
o
t
h
e
r
w
i
s
e
.Proof.
We can see in Table2 that λ
(
C
10
⊠
P
5
)
=
12 hence, it follows by Lemma 1 that λ
(
C
10
⊠
C
m
)
≥
12. The results for m
≤
26 are given in Table 2.
The following pattern represents a12
-
L
(
2,1
)-labeling of C
10
⊠
C
37, while the leftmost 12 columns of the pattern represents a 12
-
L
(
2,1
)-labeling of C
10
⊠
C
12:
8
3
1
12
8
5
7
2
0
11
9
6
8
3
1
12
10
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
3
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
4
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
9
6
3
1
12
10
5
7
12
10
5
7
4
0
11
9
4
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
5
7
2
0
11
9
6
8
3
1
6
8
3
1
12
8
5
7
2
0
11
9
6
8
3
1
12
10
5
7
4
2
0
11
6
8
3
1
12
10
5
7
4
2
0
11
9
2
0
11
9
6
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
10
7
4
2
0
11
9
6
8
3
1
12
10
5
7
4
10
5
7
4
0
11
9
4
8
3
1
12
10
5
7
4
2
0
11
6
8
3
1
12
10
5
7
4
2
0
11
9
6
8
3
1
12
By Lemma2, we have λ
(
C
10
⊠
C
12
α
+
37
β
)
≤
12 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
C
10
⊠
C
m
)
≤
12 for m
≥
(
37
-
1
)
·
(
12
-
1
)
=
396.
We have found13
-
L
(
2,1
)-labelings of C
10
⊠
C
m for 27
≤
m
≤
46 and we can construct 13
-
L
(
2,1
)-labelings of C
10
⊠
C
m for m
≥
36 as follows. We have found 13
-
L
(
2,1
)-labelings of C
10
⊠
C
25, C
10
⊠
C
50, C
10
⊠
C
27, C
10
⊠
C
28, C
10
⊠
C
29, C
10
⊠
C
54, and C
10
⊠
C
39. Any of these labelings restricted to the first eight copies of C
10 is a 13
-
L
(
2,1
)-labeling of C
10
⊠
C
8. From Lemma 2 it follows that λ
(
C
10
⊠
C
8
k
)
≤
13 for k
≥
1, λ
(
C
10
⊠
C
8
k
+
1
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
2
)
≤
13 for k
≥
6, λ
(
C
10
⊠
C
8
k
+
3
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
4
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
5
)
≤
13 for k
≥
3, λ
(
C
10
⊠
C
8
k
+
6
)
≤
13 for k
≥
6, and λ
(
C
10
⊠
C
8
k
+
7
)
≤
13 for k
≥
4. These observations complete the proof.Proposition 19.
λ
(
C
11
⊠
C
m
)
=
10 only if m
≡
0
(
mod
⁡
11
).Proof.
The graphD
11,10
2 with 380 vertices and the largest outdegree 2 has been computed. Since breadth first search algorithm has found only cycles of length length 11, Theorem 9 yields the proof.Theorem 20.
Ifm
≥
11, then
(12)
λ
(
C
11
⊠
C
m
)
=
{
10
,
m
≡
0
(
mod
⁡
11
)
12
,
m
∈
{
12,13,14,15,16,18,19
,

20,21,22,23,25,26
}
11
m
≥
270
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
∈
{
12,13,14,15,16,18,19,20,21,22,23,25,26
} the λ numbers are obtained by using the SAT reduction as depicted in Table 1. Since λ
(
C
11
⊠
P
3
)
=
10, from Lemma 1 it follows that λ
(
C
11
⊠
C
m
)
≥
10, while from Proposition 19 it follows that λ
(
C
11
⊠
C
m
)
≥
11 if m
≢
0 (mod 11).
The result form
≡
0
(
mod
⁡
11
) can be obtained by the fact that λ
(
C
11
⊠
C
11
)
=
10 and by Lemma 2.
Figure6 represents an 11
-
L
(
2,1
)-labeling of C
11
⊠
C
28, where the leftmost 11 columns of the figure represent an 11
-
L
(
2,1
)-labeling of C
11
⊠
C
11. By Lemma 2, we have λ
(
C
11
⊠
C
11
α
+
28
β
)
≤
11 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
C
11
⊠
C
m
)
≤
11 for m
≥
(
28
-
1
)
·
(
11
-
1
)
=
270.
In order to find the general upper bound, we present the constructions showing thatλ
(
C
11
⊠
C
m
)
≤
12 for m
≥
26. In particular, Figure 7 shows a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
37. This labeling restricted to the first 12 copies of C
11 induces a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
12. From Lemma 2 it follows that λ
(
C
11
⊠
C
12
k
+
1
)
≤
12, k
≥
3, and λ
(
C
11
⊠
C
12
k
)
≤
12, k
≥
1.
Analogously, we have found12
-
L
(
2,1
)-labelings of C
11
⊠
C
38, C
11
⊠
C
39, C
11
⊠
C
40, C
11
⊠
C
41, C
11
⊠
C
42, C
11
⊠
C
43, C
11
⊠
C
44, C
11
⊠
C
45, C
11
⊠
C
46, and C
11
⊠
C
35. Any of these labelings restricted to the first 12 copies of C
11 is a 12
-
L
(
2,1
)-labeling of C
11
⊠
C
12.
From Lemma2 it follows that λ
(
C
11
⊠
C
12
k
+
2
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
3
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
4
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
5
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
6
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
7
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
8
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
9
)
≤
12 for k
≥
3, λ
(
C
11
⊠
C
12
k
+
10
)
≤
12 for k
≥
3, and λ
(
C
11
⊠
C
12
k
+
11
)
≤
12 for k
≥
2.
Since we have also found12
-
L
(
2,1
)-labelings of C
11
⊠
C
27, C
11
⊠
C
28, C
11
⊠
C
29, C
11
⊠
C
30, C
11
⊠
C
31, C
11
⊠
C
32, C
11
⊠
C
33, and C
11
⊠
C
34, we establish that λ
(
C
11
⊠
C
m
)
≤
12 for all m
≥
27 and the proof is complete.Figure 6
11
-
L
(
2,1
)-labeling of C
11
⊠
C
28.Figure 7
12
-
L
(
2,1
)-labeling of C
11
⊠
C
37.


## 4.3.λ-Numbers of P
n
⊠
C
m

Proposition 21.
Ifm
≥
3, then
(13)
λ
(
P
3
⊠
C
m
)
=
{
14
,
m
=
5
11
,
m
∈
{
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}
10
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results are obtained by solving the SAT instances transformed from the corresponding L
(
2,1
)-labeling problems (see Table 1).
The graphD
3,10
′
2 with 9080 vertices and the largest outdegree 16 has been created in order to find 10
-
L
(
2,1
)-labelings in P
3
⊠
C
m. Matrix multiplication has been applied in order to find closed directed walks in the graph. The algorithm has found no closed directed walk of length from the set {
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}
∪
{
5
}. It follows that λ
(
P
3
⊠
C
n
)
≥
11 for any m
∈
{
3,4
,
6,7
,
8,9
,
10,13,14,18,19
}. The upper bounds for m
∈
{
13,14,18,19
} follow from the labelings depicted in Figure 8.
We have found10
-
L
(
2,1
)-labelings of P
3
⊠
C
23, P
3
⊠
C
35, P
3
⊠
C
47, P
3
⊠
C
26, P
3
⊠
C
38, P
3
⊠
C
39, P
3
⊠
C
40, P
3
⊠
C
41, P
3
⊠
C
31, and P
3
⊠
C
43. Any of these labelings restricted to the first 11 copies of P
3 is a 10
-
L
(
2,1
)-labeling of P
3
⊠
C
11. From Lemma 2 it follows that λ
(
P
3
⊠
C
11
k
)
≤
10 for k
≥
1, λ
(
P
3
⊠
C
11
k
+
1
)
≤
10 for k
≥
2, λ
(
P
3
⊠
C
11
k
+
2
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
3
)
≤
10 for k
≥
4, λ
(
P
3
⊠
C
11
k
+
4
)
≤
10 for k
≥
2, λ
(
P
3
⊠
C
11
k
+
5
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
6
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
7
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
8
)
≤
10 for k
≥
3, λ
(
P
3
⊠
C
11
k
+
9
)
≤
10 for k
≥
2, and λ
(
P
3
⊠
C
11
k
+
10
)
≤
10 for k
≥
3.
Since we have also found10
-
L
(
2,1
)-labelings of P
3
⊠
C
13, P
3
⊠
C
14, P
3
⊠
C
15, P
3
⊠
C
16, P
3
⊠
C
17, P
3
⊠
C
18, P
3
⊠
C
19, P
3
⊠
C
20, P
3
⊠
C
21, P
3
⊠
C
24, P
3
⊠
C
25, P
3
⊠
C
27, P
3
⊠
C
28, P
3
⊠
C
29, P
3
⊠
C
30, P
3
⊠
C
32, and P
3
⊠
C
36, we establish that λ
(
P
3
⊠
C
m
)
≤
10 for all m
≥
13 and the proof is complete.(a)11
-
L
(
2,1
)-labeling of P
3
⊠
C
3, (b) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
4, (c) 14
-
L
(
2,1
)-labeling of P
3
⊠
C
5, (d) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
7, (e) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
13, and (f) 11
-
L
(
2,1
)-labeling of P
3
⊠
C
19.
(a)
(b)
(c)
(d)
(e)
(f)Proposition 22.
Ifm
≥
3, then
(14)
λ
(
P
4
⊠
C
m
)
=
{
14
,
m
=
5
10
,
m
≡
0
(
mod
⁡
11
)
11
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
=
5 the result is obtained by solving the SAT instance transformed from the corresponding L
(
2,1
)-labeling problem. For m
≡
0
(
mod
⁡
11
) the result follows from Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
In order to find10
-
L
(
2,1
)-labelings in P
4
⊠
C
m, the graph D
4,10
′
2 with 16792 vertices and the largest outdegree 3 has been created. Since breadth first search algorithm has found only cycles of length 11, the upper bound follows.
For allm
≢
0
(
mod
⁡
11
) and m
≥
13 we can construct 11
-
L
(
2,1
)-labelings of P
4
⊠
C
m as described below. We have found 11
-
L
(
2,1
)-labelings of P
4
⊠
C
13, P
4
⊠
C
14, P
4
⊠
C
15, P
4
⊠
C
16, and P
4
⊠
C
17. Any of these labelings restricted to the first six copies of P
4 is an 11
-
L
(
2,1
)-labeling of P
4
⊠
C
11. From Lemma 2 it follows that λ
(
P
4
⊠
C
6
k
+
1
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
2
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
3
)
≤
11 for k
≥
2, λ
(
P
4
⊠
C
6
k
+
4
)
≤
11 for k
≥
2, and λ
(
P
4
⊠
C
6
k
+
5
)
≤
11 for k
≥
2. These conclusions complete the proof.Corollary 23.
Letn
,
m
≥
4.(i)
Ifm
≢
0
(
mod
⁡
11
), then
λ
(
P
n
⊠
C
m
)
≥
11,
(ii)
Ifn
≢
0
(
mod
⁡
11
)  or
m
≢
0
(
mod
⁡
11
), then
λ
(
C
n
⊠
C
m
)
≥
11.From Theorem6 now we have the followingCorollary 24.
Ifm
≥
24 and n
≥
26, then
(15)
λ
(
C
n
⊠
C
m
)
=
{
10
,
n
≡
0
(
mod
⁡
11
)

m
≡
0
(
mod
⁡
11
)
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proposition 25.
Ifm
≥
3, then
(16)
λ
(
P
5
⊠
C
m
)
=
{
14
,
m
=
5
12
,
m
=
3,9
,
10
10
,
m
≡
0
(
mod
⁡
11
)
11
,
m
=
4,6
,
7,8
,
12
o
r
m
≥
80
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results follow from Table 1. For m
≡
0
(
mod
⁡
11
) the result follows from Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
Figure9 represents an 11
-
L
(
2,1
)-labeling of P
5
⊠
C
17, where the leftmost six columns of the figure represent an 11
-
L
(
2,1
)-labeling of P
5
⊠
C
6.
By Lemma2, we have λ
(
P
5
⊠
C
6
α
+
17
β
)
≤
11 for integers α and β. Finally, thanks to Lemma 3, we get λ
(
P
5
⊠
C
m
)
≤
11 for m
≥
(
17
-
1
)
·
(
6
-
1
)
=
80.
In order to complete the proof note that from Theorem16 and Lemma 1 it follows that λ
(
P
5
⊠
C
m
)
≤
12 for m
≥
11.Figure 9
11
-
L
(
2,1
)-labeling of P
5
⊠
C
17.Proposition 26.
Ifm
≥
3, then
(17)
λ
(
P
6
⊠
C
m
)
=
{
14
,
m
=
5
12
,
m
=
3,9
,
10
10
,
m
≡
0
(
mod
⁡
11
)
11
,
m
=
4,6
,
7,8
,
12
o
r
m
≥
154
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.Proof.
Form
≤
12 the results follow from Table 1. For m
≡
0
(
mod
⁡
11
) the result follows Lemma 2 and from the fact that λ
(
C
11
⊠
C
11
)
=
10.
Figure10 represents a 11
-
L
(
2,1
)-labeling of P
6
⊠
C
23, where the leftmost eight columns of the figure represent an 11
-
L
(
2,1
)-labeling of P
6
⊠
C
8.
By Lemma2, we have λ
(
P
6
⊠
C
8
α
+
23
β
)
≤
11 for integers α and β. From Lemma 3 it follows that λ
(
P
6
⊠
C
m
)
≤
11 for m
≥
(
23
-
1
)
·
(
8
-
1
)
=
154.
We complete the proof by noting that from Theorem16 and Lemma 1 it follows λ
(
P
6
⊠
C
m
)
≤
12 for m
≥
11.Figure 10
11
-
L
(
2,1
)-labeling of P
6
⊠
C
23.Values in Table1, the results from Section 4.2, Theorems 6 and 20, and Corollary 23 provide lower and upper bounds for the λ-number of P
n
⊠
C
m. The results are summarized in the following.Theorem 27.
Ifn
≥
7, then
(18)
λ
(
P
n
⊠
C
m
)
=
{
10
,
m
≡
0
(
mod
⁡
11
)
14
,
m
=
5
12
,
m
=
3,7
,
9,10
11
,
m
=
4,6
,
8,12
o
r
m
≥
270
11
o
r
12
,
o
t
h
e
r
w
i
s
e
.


## 5. Conclusion

In this paper, theL
(
2,1
)-labeling problem of the strong product of paths and cycles is studied. The problem derives from the more general Frequency Assignment Problem (FAP) which requires assigning frequencies to transmitters in a wireless network. It is well known that some interesting wireless networks are closely connected to the strong product of graphs. For example, an octagonal grid is the strong product of two paths and an octagonal torus is the strong product of two cycles.By using various computational approaches, we succeed in solving the problem (except for the final number of cases) for the strong product of a path and a cycle, as well as for the the strong product of two cycles, where one of the cycles is of length at most eleven. Moreover, the obtained results enable us to improve the bounds on theλ-number for the strong product of two cycles, where both cycles are sufficiently long. Finding the exact λ-numbers for these graphs is therefore an interesting and challenging avenue of further research.



---

*Source: 741932-2014-02-24.xml*