1. Introduction
Let
be a graph. For two vertices u and v in G, the distance between u and v is the number of the edges of the shortest path between u and v. A k-L(2,1)-labeling for a graph G is a function
such that
whenever
and
whenever u and v are at distance two apart. The λ-number for G, denoted by
, is the minimum k over all k-L(2,1)-labelings of G. This labeling problem of graphs was proposed by Griggs and Roberts [1] which is a variation of the frequency assignment problem introduced by Hale [2] . The frequency assignment problem asks for assigning frequencies to transmitters in a broadcasting network with the aim of avoiding undesired interference. One of the graph theoretical models of the frequency assignment problem is the notion of distance constrained labeling of graphs [3] [4] [5] .
The L(2,1)-labeling problem was studied very extensively in the literature and has attracted much attention. Griggs and Yeh [6] proposed a conjecture, which is called the
-conjecture, that
for any graph with
, where
is the maximum degree of G, and they also proved that
. Later, it was shown that
by Chang and Kuo [7] ,
by Král’ and Škrekovski [8] , and then
by Goncalves [9] . Until now, this conjecture is still open. Nevertheless, it is still interesting to study the
-conjecture, which has been confirmed for several classes of graphs, such as chordal graphs, outerplanar graphs, generalized Petersen graphs, Hamiltonian graphs with
, two families of Hamming graphs etc (see [10] ). Havet et al. obtained a result implying that the
-con- jecture is true for graphs with sufficiently large
. Thus, we may need to study the L(2,1)-labelling problem for graphs with small
. Motivated with this, the L(2,1)-labelling problem for the brick product graphs was studied [10] .
Let
,
and
be integers such that
is even. Let
be a cycle of length
. The
-brick-product of
, denoted by
, is the graph with adjacency defined in two cases. For
must be odd and
is obtained from the cycle
by adding chords joining
and
for
, where subscripts are taken modulo
. In the general case where
,
is obtained by first taking the vertex-disjoint union of m copies of
, denoted by
(1)
Next, for each pair
such that i and j have the same parity, an edge is added to join
and
. Finally, for odd
, an edge is added to join
and
, where the second subscript is modulo
.
Li et al. [10] proposed the following conjecture:
Conjecture 1. [10]
or 6 for all brick products
with
and ![]()
Shao et al. [11] confirmed the above conjecture, i.e. it was proved that
Theorem 1. [11]
if 1)
is even, or 2)
is odd and
.
Therefore, Conjecture 1 is still open for odd
and
.
In this paper, we show that
for
or 11, which con- firms Conjecture 6.1 stated in [X. Li, V. Mak-Hau, S. Zhou, The L(2,1)-labelling problem for cubic Cayley graphs on dihedral groups, J. Comb. Optim. (2013) 25: 716-736] in the case when
or 11. Moreover, we show that
if 1) either
(mod 6), m is odd,
, 2) or
(mod 3), m is even (mod 2),
.
2. Main Results
From the definition of the brick product graph, it is clear that
Fact 1.
is isomorphic to
.
2.1. Some Results on the Upper Bound 6 of l-Number
In [6] , it was shown that
Lemma 1. [6] The λ-number of any connected cubic graph is at least 5.
Proposition 1. Let
. Then
for all
.
By Theorem 1, we have
for all
and
. Toge- ther with Fact 1, we only need to consider
. Let
![]()
We use the pattern
to label
for
, and
in- duces a 6-L(2,1)-labeling of
. Therefore, the case
is settled.
![]()
Now, we consider the case
. If
for
, we obtain a 6- L(2,1)-labeling of
by repeating the leftmost four columns of
; If
for
, we obtain a 6-L(2,1)-labeling of
by re- peating the leftmost four columns of
(see Figure 1). Therefore,
for
and
.
Proposition 2. Let
. Then
for all
.
Similar to Proposition 1, we only need to consider the case
and 11.
Case 1:
.
We use the following pattern
to label
for
, and
induces a 6-L(2,1)-labeling of
. Therefore, the case
is settled. Now, we consider the case
. If
for
, we obtain a 6-L(2,1)-labeling of
by repeating the leftmost four columns of
; If
for
, we obtain a 6-L(2,1)-labeling of
by re- peating the leftmost four columns of
. Therefore,
for
and
.
![]()
Figure 1. The 6-L(2,1)-labeling of
induced by
.
![]()
![]()
Case 2:
.
We use the following pattern
to label
for
, and
induces a 6-L(2,1)-labeling of
. Therefore, the case
is settled. Now, we consider the case
. If
for
, we obtain a 6-L(2,1)-labeling of
by repeating the leftmost four columns of
; If
for
, we obtain a 6-L(2,1)-labeling of
by repeating the leftmost four columns of
. Therefore,
for
and
.
From Propositions 1 and 2, we have
Theorem 2. Let
. Then we have
for
or 11.
2.2. Brick Product Graphs with l-Number 5
In [10] , it was proved that
Theorem 3. Let
and
be integers such that
. Then
.
Moreover,
if and only if one of the following holds:
1) 3 divides
and 6 divides m;
2) 6 divides
and 3 divides m.
Furthermore, if neither 1) nor 2) is satisfied, then
pro- vided that
(and
is even or odd), or both
and m are even.
However, Theorem 3 consider the condition that
. There may exist other brick product graphs with λ-number 5 with the condition
. We provide some brick product graphs
with l-number 5 in the following:
Theorem 4. Let
,
with
,
. Then
.
Let
,
,
and
, where
is used for
times. Then Q induces a 5-L(2,1)-labeling of
, and so
.
Proposition 3. Let
,
,
. Then
.
Let
, and
, where P is used for
times. Then Q
induces a 5-L(2,1)-labeling of
, and so
.
Proposition 4. Let
,
,
. Then
.
Let
, and
, where P is used for
times.
Then Q induces a 5-L(2,1)-labeling of
, and so
.
Proposition 5. Let
,
,
. Then
.
Let
, and
, where P is used for ![]()
times. Then Q induces a 5-L(2,1)-labeling of
, and so
.
Proposition 6. Let
, m = 9, r = 3. Then
.
Let
, and
, where P is used for
times. Then Q induces a 5-L(2,1)-labeling of
, and so
.
By observing the results of Propositions 3 - 6, we propose the following con- jecture:
Conjecture 2. Let
,
,
. Then
.
Acknowledgements
This work was supported by Applied Basic Research (Key Project) of Sichuan Province under grant 2017JY0095, Key Project of Sichuan Provincial Department of Education under grant 17ZA0079 and Automotive Creative Design Pilot Area of Chengdu University and Longquanyi District under grant 2015-CX00- 00010-ZF.