=Paper=
{{Paper
|id=Vol-3072/paper15
|storemode=property
|title=L(2,1)-Edge Labeling of Infinite Triangular Grid
|pdfUrl=https://ceur-ws.org/Vol-3072/paper15.pdf
|volume=Vol-3072
|authors=Susobhan Bandopadhyay,Sasthi C. Ghosh,Subhasis Koley
|dblpUrl=https://dblp.org/rec/conf/ictcs/BandopadhyayGK21
}}
==L(2,1)-Edge Labeling of Infinite Triangular Grid==
https://ceur-ws.org/Vol-3072/paper15.pdf
L(2, 1)-edge labeling of Infinite Triangular Grid?
Susobhan Bandopadhyay1 , Sasthi C. Ghosh2 , and Subhasis Koley2
1
National Institute of Science Education and Research, HBNI, Bhubaneswar, India,
Email: susobhan.bandopadhyay@niser.ac.in
2
Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India,
Emails: sasthi@isical.ac.in, subhasis.koley2@gmail.com
Abstract. An L(h, k)-edge labeling of a graph G is the assignment of labels
{0, 1, · · · , n} to the edges in such a way that two adjacent edges get labels with
a difference at least h and the labels of distance two edges, i.e., two non-adjacent
edges having a common edge connecting them get labels with a difference at
least k, where h and k are two given non-negative integers. The span λ0h,k (G)
is the minimum n such that G admits an L(h, k)-edge labeling. For three given
integers n, h and k, an n-circular-L(h, k)-edge labeling f 0 of a graph G is an
assignment from integers {0, 1, · · · , n − 1} in such a way that if two edges e and
e0 are adjacent then |f 0 (e) − f 0 (e0 )|n ≥ h and if they are distance two edges then
|f 0 (e) − f 0 (e0 )|n ≥ k, where |x|n = min{x, n − x}. The circular span σh,k 0
(G)
is the minimum n such that G admits an n-circular L(h, k)-edge labeling. Here,
we focus on finding λ02,1 (G) and σ2,1 0
(G) where G is infinite regular triangular
grid T6 . We work on the conjecture λ02,1 (T6 ) = 16 and the bound σ2,1 0
(T6 ) ≤ 18
given by Lin and Wu [J. Comb. Opt., 2013]. We prove the conjecture and give
0
a labeling function for T6 such that σ2,1 (T6 ) ≤ 18 as no labeling function was
given by Lin and Wu in this case.
Keywords: Channel assignment problem · L(2, 1)-labeling · infinite grids · lower
bound · upper bound.
1 Introduction
In wireless communication, Channel Assignment Problem (CAP) is known as one of the
fundamental and well-studied problems where the goal is to assign frequency channels
to transmitters such that interference cannot occur. The target of this problem is to
minimize the span of frequency spectrum, where the span is the difference between the
lowest and highest frequencies used in the assignment. The formulation of CAP has
been done in 1980 by Hale [1]. He formulated CAP as a vertex coloring problem. Then
Roberts [2], in 1988, introduced the notion of L(h, k)-vertex labeling as defined below:
Definition 1. For two non-negative integers h and k, an L(h, k)-vertex labeling of a
graph G(V, E) is a function f : V → − {0, 1, · · · , n}, ∀v ∈ V such that |f (u)−f (v)| ≥ h
when d(u, v) = 1 and |f (u) − f (v)| ≥ k when d(u, v) = 2. Here, distance between
vertices u and v, d(u, v) is k 0 if at least k 0 edges are required to connect u and v.
?
Copyright c 2021 for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0).
2 S. Bandopadhyay et al.
The span λh,k (G) of L(h, k)-vertex labeling is the minimum n such that G admits an
L(h, k)-vertex labeling. After some good years, Griggs and Yeh [9] extended the con-
cept by introducing L(k1 , k2 , · · · , k` )-vertex labeling with separations k1 , k2 , · · · , k`
for 1, 2, · · · , ` distant vertices respectively and their main focus was on L(h, k)-vertex
labeling for a special case h = 2, k = 1. Griggs and Jin [8] in 2007 studied L(h, k)-
edge labeling, which can be formally defined as:
Definition 2. For two non-negative integers h and k, an L(h, k)-edge labeling of a
graph G(V, E) is a function f 0 : E → − {0, 1, · · · , n}, ∀e ∈ E such that |f 0 (e1 ) −
f (e2 )| ≥ h when d(e1 , e2 ) = 1 and |f 0 (e1 ) − f 0 (e2 )| ≥ k when d(e1 , e2 ) = 2. Here,
0
for any two edges e1 and e2 , the distance d(e1 , e2 ) is k 0 if at least (k 0 − 1) edges are
required to connect e1 and e2 .
Like L(h, k)-vertex labeling, the span λ0h,k (G) of L(h, k)-edge labeling is the mini-
mum n such that G admits an L(h, k)-edge labeling. In 2011, Calamoneri did a rig-
orous survey [7] on both vertex and edge labeling problems. A regular grid graph is
a graph which is constructed by tessellation of regular two dimensional polygon in a
two dimensional plane. Regular grids are a natural choice of modelling CAP for their
symmetric geometric pattern and thus study of L(h, k) labeling of regular grids have a
relevance both in theory and in practice. Authors in [3–6] have studied L(h, k)-edge
labeling of regular infinite hexagonal (T3 ), square (T4 ), triangular (T6 ) and octagonal
(T8 ) grids for the special cases h = 1, k = 2 and h = 2, k = 1. They obtained some
upper and lower bounds on λ01,2 (G) for T3 , T4 , T6 and T8 with a gap between them.
Later on, Bandopadhyay et al. [10] improved some bounds on T3 , T4 and T6 .
In the year 1998 Van den Heuvel [11] introduced another interesting variant of the
L(h, k)-labeling called circular-L(h, k)-labeling. An n-circular-L(h, k)-labeling can
be formally defined as follows:
Definition 3. For three given non-negative integers n, h and k, n-circular-L(h, k)-
labeling f of a graph G is an assignment from integers {0, 1, · · · , n − 1} in a way that
if two vertices u and v are adjacent, then |f (u)−f (v)|n ≥ h and if they are distance two
apart then |f (u) − f (v)|n ≥ k, where |x|n = min{x, n − x}. Moreover, the minimum n
such that G admits an n-circular-L(h, k)-labeling is called the circular span σh,k (G).
Authors in [11] gave the circular span for T3 and T4 and also gave the following Lemma:
Lemma 1. For a graph G(V, E) and for two given non-negative integers h and k such
that h ≥ k, we can write, λh,k (G) + 1 ≤ σh,k (G) ≤ λh,k (G) + h.
Naturally this problem as well as the Lemma have their corresponding an edge
versions. As in this paper our main work in on edge labeling, we discuss those formally.
Definition 4. For three given non-negative integers n, h and k, an n-circular-L(h, k)-
edge labeling f 0 of graph G is an assignment from integers {0, 1, · · · , n − 1} in a way
that if two edges e and e0 are adjacent, then |f 0 (e) − f 0 (e0 )|n ≥ h and if they are
distance two apart, then |f 0 (e) − f 0 (e0 )|n ≥ k, where |x|n = min{x, n − x}. Moreover,
the minimum n such that G admits an n-circular-L(h, k)-edge labeling is called the
0
circular span σh,k (G).
L(2, 1)-edge labeling of Infinite Triangular Grid 3
The edge version of the Lemma 1 is
Lemma 2. For a graph G(V, E) and for two given non-negative integers h and k such
that h ≥ k, we can write, λ0h,k (G) + 1 ≤ σh,k
0
(G) ≤ λ0h,k (G) + h.
Lin and Wu [3] studied regular infinite hexagonal (T3 ), square (T4 ) and triangular
(T6 ) grids for the edge versions of L(h, k)-labeling and circular-L(h, k)-labeling for
h = 2 and k = 1. They conjectured on the triangular grids as given below:
Conjecture 1. λ02,1 (T6 ) = 16.
0
They also gave the bound σ2,1 (T6 ) ≤ 18.
1.1 Our Contributions
In this paper we first focus on the Conjecture 1. We show that λ02,1 (T6 ) = 16. We also
0
give a labeling function for T6 such that σ2,1 (T6 ) ≤ 18 as no labeling function was
given by Lin and Wu [3] in this case.
Table 1: The result regarding λ02,1 (T6 ). *The proof of lower bound for λ02,1 (T6 ) stated
in [12] is incorrect. They proved λ02,1 (H 00 ) ≥ 16 where H 00 is the subgraph of T6 as
shown by the bold edges in Figure 1. But we have shown that λ02,1 (G) ≤ 15 as shown
in Figure 1. Note that H 00 is a subgraph of G.
λ02,1 (G)
Grid Known Ours
T6 15-16 [3], (16-16) [12]* 16-16
u1 u2 u3 u4
3 15 4 9 0 8
u5 v1 v2
10 11 v3 14 u6
13
4 7 0 6
1 5 2 9
u7
11 v4 14 v5 12 v6 15 v7 13 u8
9 1 8 2 7 3 6 4
u9 v8 v9 v10 u10
15 13 11 14
5 3 9 4 8 0
u11 v11 v u12
14 12 12 10
6 0 15 1
u13 u14 u15
Fig. 1: Coloring of G with colors {0, 1, · · · , 15}.
4 S. Bandopadhyay et al.
u1 u2 u3 u4
y17 y18 y19 y20 y21 y22
u5 y16 v1 x8 v2 x9 v3 y23 u6
y15 x7 a n d k x1 y24
u7 y v4 h v5 g v6 f v7 y1 u8
14
y13 x6 o b l e x2 y2
u9 y12 v8 j v9 i v10 y3 u10
y11 x5 m c x3 y4
u11 y10 v11 x4 v12 y5 u12
y9 y8 y7 y6
u13 u14 u15
Fig. 2: Graph G
2 Results for L(2, 1)-edge labeling
For a vertex v, let N (v) denotes the set of neighbors of v and for a set of vertices S, let
N (S) = ∪ N (v). Consider the subgraph G(V, E) of T6 centering the triangle formed
v∈S
by S = {v5 , v6 , v9 } as shown in Figure 2, where V = S ∪ N (S) ∪ N (N (S)) and E is
the set of all edges which are incident to u where u ∈ S ∪ N (S). Now, we define the
set of edges in G into five subsets of edges as following:
S1 = {g, b, l}
S2 = {d, e, n, o, i, j}
S3 = {k, f, a, h, m, c}
S4 = {x1 , x2 , x3 , · · · , x9 }
S5 = {y1 , y2 , y3 , · · · , y24 }
Our proof approach is as follows. In first few observations and lemma (Observa-
tion 1, Observations 2, Observations 3, Observation 4 and Lemma 3) we first investigate
if a color c0 is used in S1 or in S2 or in S3 , then how many times at maximum it can
be reused in G and repetition pattern of the colors such that edges of G can be colored
with 15(0, 1, · · · , 14) colors. In Observation 5, we determine the maximum number of
times a color c0 can be used in G if it is not used in S1 ∪ S2 ∪ S3. In subsequent
observation and lemmas(Observation 6, Lemma 4, Lemma 5) we discuss the scenario
when a color c0 ∈ / {5, 10} is unused in S1 ∪ S2 ∪ S3 and two consecutive colors c0 and
0
c + 1 are used in different types of edges. Based on the discussion and results of the
mentioned observations and lemmas, we determine the lower bound of λ02,1 (T6 ) when a
color cu ∈/ {5, 10} is unused in S1 ∪ S2 ∪ S3 in Theorem 1, Theorem 2 and Theorem 3.
In Theorem 4, we determine the lower bound of λ02,1 (T6 ) when a color cu ∈ {5, 10}
is unused in S1 ∪ S2 ∪ S3 . In Theorem 5, we determine the lower bound of λ02,1 (T6 )
when all colors in {0, 1, · · · , 14} are used in S1 ∪ S2 ∪ S3 . In all the cases, derived
lower bounds of λ02,1 (T6 ) are identical.
L(2, 1)-edge labeling of Infinite Triangular Grid 5
Observation 1 Let c0 be any color used at an edge in S1 , then c0 can be used at most
once more in G.
Proof. Without loss of generality, assume that c0 is used in the edge g. Now, it is clear
that c0 can only be used in some edges incident to v11 and v12 . Since, edges incident
to v11 and v12 are not mutually three distance apart, c0 can only be used at most in one
edge.
Observation 2 Let c0 be any color used in an edge in S2 , then c0 can be used in at most
two more times in G.
Proof. As all the edges in S2 are in symmetric position, without loss of generality we
can assume that c0 is used in the edge d. One can verify that some edges incident to
v4 , v8 , v11 , v12 only are distant three from d. Note that v4 and v8 are adjacent to each
other. Similarly v11 and v12 are also mutually adjacent. Hence c0 can be used two times,
once in an edge incident to v4 , v8 and the other in an edge incident to v11 , v12 . But if c0
is used in x5 , then c0 cannot be used once more.
Observation 3 Let c0 be any color used at an edge in S3 , then c0 can be used in at most
three more edges in G.
Proof. Observe that here also all the edges are symmetric, so, without loss of gener-
ality we can assume that c0 is used at the edge k. Some edges adjacent to the vertices
v1 , v4 , v8 , v11 , v12 only are three distance apart from k. It is clear that c0 can be used at
the edges adjacent to alternate vertices in the sequence v1 , v4 , v8 , v11 , v12 . Moreover, it
can be observed that each edge in S4 where c0 can be used is adjacent to two vertices in
v1 , v4 , v8 , v11 , v12 . So, if we want to use c0 three more times in G, then c0 must be used
at edges adjacent to v1 , v8 , v12 , and the color must be used at edges in S5 only.
From Observations 1, 2 and 3 it is clear that colors used to color the edges in S1 , S2
and S3 can be used at most two, three and four times in G, respectively. Note that G
has 48 edges in total. We need all distinct colors to color the edges in S1 ∪ S2 ∪ S3
as they are mutually at most two distance apart. So, we need 3, 6 and 6 distinct colors
to color the edges in S1 , S2 and S3 , respectively. If we can repeat all these color with
their maximum potential, then it is possible to color the graph G using 15 colors. Here
we state Observation 4 and give the unique repetition pattern of the colors, to color
G using 15 colors in Lemma 3. Let H be the subgraph of G induced by the edges in
S1 ∪ S2 ∪ S3 . We say two edges e1 = (u1 , v1 ) and e2 = (u2 , v2 ) as a pair of opposite
edges iff d(e1 , e2 ) = 3, d(u1 , u2 ) = 2, d(u1 , v2 ) = 2, d(v1 , u2 ) = 2 and d(v1 , v2 ) = 2.
Observation 4 If a color c0 is used in an edge e1 in T6 and is not used at the opposite
edge of e1 , then there exists a subgraph H 0 isomorphic to H where c0 cannot be used.
Proof. Without loss of generality let us consider the pair of opposite edges n and x2
(Figure 2). Let f 0 (n) = c0 and f 0 (x2 ) 6= c0 . Consider the two triangles {v3 , v6 , v7 } and
{v6 , v9 , v10 }. Clearly, c0 cannot be used in any edge incident to v3 , v6 and v9 . Therefore
c0 can be assigned to either an edge incident to v7 or an edge incident to v10 but not both.
So, c0 cannot be used either in the subgraph H 0 isomorphic to H with S10 = {v3 , v6 , v7 }
or in the subgraph H 00 isomorphic to H with S100 = {v6 , v9 , v10 }. Hence the proof.
6 S. Bandopadhyay et al.
Lemma 3. If G is colored with 15 colors only, then there is the following unique rep-
etition of the colors used in subgraph H: (a) each color used at the edges in S3 must
be repeated three times more in the edges of S5 , (b) each color used at the edges in S2
must be repeated two times more, once in its opposite edge in S4 and the other in an
edge in S5 , (c) each color used at the edges in S1 must be repeated once more in its
opposite edge in S4 .
Proof. Observe that the first condition for G to be colored with 15 colors is the colors
used in S1 , S2 and S3 have to be used two times, three times and four times in G
respectively. From the proof of Observation 3 it directly follows that if we want to reuse
three times a color c3 that has been used in an edge of S3 , then c3 has to be reused at the
edges of S5 only. Now assume that c2 be a color used in an edge of S2 then c2 cannot
be reused at two edges in S4 as there does not exists two mutually three distant edges in
S4 such that c2 can be used. From Observation 4 it follows that c2 should be reused at
the corresponding opposite edge in S4 and another edge in S5 . Observe that only three
edges in S4 remain uncolored now. Again from Observation 4 we can say that if c1 be
a color used in an edge of S1 , then c1 has to be reused at the corresponding opposite
edge in S4 only.
We aim to prove λ02,1 (T6 ) = 16. We already know that λ02,1 (H) = 14 and λ02,1 (T6 ) ≥
15 [3]. So, without loss of generality, we can assume that one color is unused at H. In
Observations 1, 2, 3 we showed the re-usability of the colors used at S1 , S2 and S3 ,
respectively. Now we focus on the color which is not used in H.
Observation 5 Let c0 be any color not used in H, then c0 can be used at most four
edges in G.
Proof. Clearly, c0 is used at edges in S = S4 ∪ S5 . All edges in S are incident to one
or two vertices in Q = {v1 , v2 , v3 , v7 , v10 , v12 , v11 , v8 , v4 }. So, c0 can be used at edges
adjacent to alternative vertices in the sequence Q. There are nine vertices in Q. If we
pick every alternate vertices in the sequence starting from v1 , then we end up with a set
Q1 of five vertices {v1 , v3 , v10 , v11 , v4 }. Since, v1 and v4 are adjacent in G, we can give
the color c0 to edges incident to either v1 or v4 . So, we have only four vertices whose
adjacent edges can be colored with c0 , and note that that no two edge adjacent to same
vertices can be colored with same color. Hence there are at most four edges which can
be colored with the unused color. Similarly, if we pick alternate vertices in the sequence
starting from v2 , then we end up with picking a set Q2 of four vertices {v2 , v7 , v12 , v8 }.
Again, we similarly argue that at most in four edges we can use the unused color in G.
From Figure 2 it is clear that the subgraph H consists of five vertical edges, five
horizontal edges and five slanting edges. Let us denote these three types of edges as
Tv , Th and Ts , respectively. Now, we prove some properties of colors used in these
three types of edges.
Observation 6 Let f 0 (p) = c0 and f 0 (q) = c0 + 1 where p, q ∈ E(H) and they are
different types of edges. Then there exists a H 0 isomorphic to H in T6 where either c0
or c0 + 1 cannot be used.
L(2, 1)-edge labeling of Infinite Triangular Grid 7
Proof. Let us consider p = f, q = a (Figure 2). Note that f 0 (f ) = c0 cannot be used at
any edge incident to v2 as d(v2 , v6 ) = 1. Again, c0 cannot be used at any edge incident
to v1 or v5 as f 0 (a) = c0 + 1. Hence c0 cannot be used in the subgraph H 0 isomorphic
to H centering the triangle S10 = {v1 , v2 , v5 }. In general, for any (p, q) pair in H, such
a triangle can be found by considering the two triangles with common edge p and the
two triangles with common edge q. Hence the proof.
Lemma 4. In the subgraph H, let the unused color c0 ∈ / {5, 10}. Then, there must exist
two disjoint pair of different typed edges (p, q) and (r, s) such that consecutive colors
have been used in each pair of edges and p ∈ Th , q ∈ Ts ; r ∈ Ts , s ∈ Tv .
Proof. Since, distance between any two edges in H is at most two, no color can be
repeated. We need three sets of five different colors to color each type of edges in H.
That means we need to divide the set of colors into three sets of equal size (i.e., five
colors in each set) in such a way that we can maximize the number of sets that contain
consecutive colors. We can say that the unused color divides the color set into two
parts. By pigeon hole principle, we can show that either one part contains more than
10 consecutive colors or both of them contains more than five consecutive colors as the
unused color c0 is neither 5 nor 10. In the former case, all three types of edges get color
from the larger part of the colors as it contains more than 10 colors. In the later case,
at least one type of edges get color from both the parts. So, in both the cases we get at
least two such pairs.
Lemma 5. For every (p, q) pair of edges in H where p and q are different types of
edges and consecutive colors are assigned to p and q, at least 2 edges of E(G) \ E(H)
cannot be colored with the colors used in H.
Proof. We prove this Lemma using case analysis and the cases are based on where the
edges p and q are present. Without loss of generality, we assume p ∈ Th and q ∈ Ts are
colored with z and z + 1 respectively. We can have the following cases:
– p, q ∈ S3 : Without loss of generality, let p = f and q = c. From Lemma 3 it
follows that if z is to be reused for 3 more times, then it has to be reused at edges
of S5 incident to v1 , v8 and v12 , which is not possible since c is adjacent to v12 .
Similarly, if z + 1 is to be used for 3 more times, then it has to be reused at edges
of S5 incident to v7 , v2 and v4 , which is also not possible since f is adjacent to v7 .
So, there are two edges in E(G) \ E(H) which remain uncolored with the colors
used in H.
– p ∈ S3 , q ∈ S2 : Without loss of generality, let p = h and q = e. From Lemma 3,
if z is to be used for 3 more times, then it has to be reused at edges of S5 incident to
v3 , v10 and v11 . But it is not possible since e is adjacent to v10 . Similarly, if z + 1
is to be used for 2 more times, then it has to be reused at x5 = (v8 , v11 ) of S4 and
an edge of S5 incident to v1 . It is not possible to use z + 1 at x5 as z is reused at an
edge of S5 adjacent to v11 . So, there are two edges in E(G) \ E(H) which cannot
be colored with the colors used in H.
– p, q ∈ S2 : Without loss of generality, let p = j and q = d. From Lemma 3, z is
to be reused at x8 = (v1 , v2 ) which is not possible here as edge d is adjacent to
8 S. Bandopadhyay et al.
(v1 , v2 ). Similarly, z + 1 is to be reused at x6 = (v4 , v8 ) which is also not possible
as edge j is adjacent to (v4 , v8 ). Therefore, two edges at E(G) \ E(H) cannot be
colored with the colors used in H.
– p ∈ S1 , q ∈ S3 : Without loss of generality, let p = g and q = c. From Lemma 3 it
follows that z has to be reused at x4 . But here it is not possible as z + 1 used at c.
If x4 is not left uncolored, then a color of H in {h, a, n, d, k, f } can only be used
at that edge. If f 0 (h) is used at x4 , then f 0 (h) can only be used at an edge of S5
incident to v3 but not at the edges of S5 incident to v10 and v11 . So, in that case
two edges will remain uncolored. If f 0 (n) is used at x4 , then f 0 (n) can neither be
used at x2 nor be used at an edge of S5 incident to v11 . So, in that case too, two
edges will remain uncolored. All other possibilities are symmetric to one of these
two cases.
We now consider the case when the unused color, say u of H is used at x4 . Since
u cannot be used at v8 and v10 , colors of {d, k, f, e} must be reused at the edges
{x6 , y12 , y11 , x5 } and the colors of {n, a, h, o} must be reused at the edges {x2 , y3 ,
y4 , x3 }. If f 0 (i) and f 0 (j) are reused at x9 and x8 respectively, then the edges
where colors f 0 (i) ± 1 and f 0 (j) ± 1 can be used are {f, g} and {g, h} respec-
tively. Therefore, if both f 0 (i) and f 0 (j) are reused at x9 and x8 respectively, then
f 0 (g) ± 1 = z ± 1 can only be used at {i, j}. Since z + 1 is used at c, either f 0 (i)
cannot be reused at x9 or f 0 (j) cannot be reused at x8 . Hence the unused color u of
H has to be used at x9 or x8 . Hence two edges at E(G) \ E(H) cannot be colored
with the colors used in H.
Now we will look at the difference of colors in the edges incident to same vertex.
Initially we investigate the case when the difference is at least three for every pair.
Then we consider the case when there exists at least a pair of edges with difference
exactly two. We classify the six edges incident to the same vertex as follows. We say
two such edges are at 60◦ if one is the immediate next edge of the other in clockwise
or anticlockwise direction. They are said to be at 120◦ and 180◦ if exactly one and two
edges respectively is/are there in between them. Now we subdivide the second case into
three more cases depending on the angle between them.
Lemma 6. If |f 0 (e1 ) − f 0 (e2 )| ≥ 3 for every pair of consecutive edges e1 , e2 ∈ E(T6 ),
then λ02,1 (T6 ) ≥ 16.
Proof. Let us consider the edge g = (v5 , v6 ) and without loss of generality assume
f 0 (g) = 0. To keep λ02,1 (T6 ) below 16, the colors that can be used at the remaining five
incident edges of v5 are 3, 6, 9, 12 and 15. Now the least color that can be used at any of
the five edges incident to v6 is 4. Therefore, the colors that can be used to the remaining
four edges incident to v6 are 7, 10, 13 and 16 respectively. Hence λ02,1 (T6 ) ≥ 16.
Therefore there exists at least two adjacent edges in T6 having color c1 and c2 with
|c1 − c2 | = 2.
Theorem 1. If two colors c0 and c0 + 2 have been assigned in any two adjacent edges
at an angle 60◦ in T6 , then λ02,1 (T6 ) ≥ 16.
L(2, 1)-edge labeling of Infinite Triangular Grid 9
Proof. Without loss of generality, assume f 0 (b) = c0 and f 0 (g) = c0 + 2. Observe that
c0 +1 must remain unused in H as ∀e1 ∈ E(H)\{b, g} either d(e1 , b) = 1 or d(e1 , g) =
1. From Lemma 4 and Lemma 5, there are 4 edges in E(G) \ E(H) which cannot be
colored with colors used in H. To make λ02,1 (G) below 16, c0 + 1 is to be used in those
4 edges. Without loss of generality, assume c0 + 1 has been used at the edges incident to
v1 , v3 , v8 and v12 respectively. Note that f 0 (g) = c0 + 2 cannot be used at x4 as c0 + 1
is used at an edge incident to v12 . So, f 0 (x4 ) ∈ {f 0 (a), f 0 (h), f 0 (n), f 0 (d), f 0 (f ), f 0 (k)}.
Consider the case when f 0 (x4 ) ∈ {f 0 (a), f 0 (h), f 0 (n)} as the case when f 0 (x4 ) ∈
{f 0 (d), f 0 (f ), f 0 (k)} can be proved similarly. Assume f 0 (x4 ) = f 0 (a). There are four
edges of S4 ∪ S5 incident to v10 where f 0 (a), f 0 (h), f 0 (n) and f 0 (o) can only be
used. But f 0 (a) cannot be used there as f 0 (x4 ) = f 0 (a). To make λ02,1 (G) below 16,
f 0 (x3 ) = c0 + 1 and f 0 (n), f 0 (h) and f 0 (o) are assigned to the other three edges. Simi-
larly, there are four edges of S4 ∪ S5 incident to v2 where f 0 (i), f 0 (c), f 0 (m) and f 0 (j)
can only be used. Now observe that f 0 (b) = c0 cannot be used at x1 as c0 + 1 is used at
an edge incident to v3 . Again, {f 0 (n), f 0 (h), f 0 (o)} and {f 0 (i), f 0 (c), f 0 (m), f 0 (j)} can-
not be used at x1 as they are used at edges incident to v10 and v2 respectively. Hence
f 0 (x1 ) = f 0 (a). Proceeding similarly we can show that f 0 (x9 ) = f 0 (i), f 0 (x8 ) = f 0 (j),
f 0 (x7 ) = f 0 (l) and f 0 (x5 ) = f 0 (e). Now observe that f 0 (a) and f 0 (x) are used at two
adjacent vertices for all x ∈ E(H) \ {d}. Therefore one of f 0 (a) ± 1 cannot be used in
H. Moreover, none of f 0 (a) ± 1 can be the unused color c0 + 1 as c0 and c0 + 2 are used
at b and g respectively. Hence λ02,1 (G) ≥ 16.
Theorem 2. If two colors c0 and c0 + 2 have been assigned in any two adjacent edges
at an angle 120◦ in T6 , then λ02,1 (T6 ) ≥ 16.
Proof. Without loss of generality, assume f 0 (g) = c0 and f 0 (e) = c0 + 2 (Figure 2).
There may be two cases, when c0 + 1 is used in H and when c0 + 1 is not used in
H. First consider the second case. From Lemma 4, there are 4 edges in E(G) \ E(H)
which cannot be colored with the colors used in H. To make λ02,1 (G) below 16, c0 + 1
is to be used in those 4 edges. Without loss of generality, assume c0 + 1 is used in
edges in E(G) \ E(H) adjacent to vertices v1 , v3 , v8 and v12 respectively. Note that
f 0 (x4 ) 6= f 0 (g) = c0 as c0 + 1 is used in an edge adjacent to v12 . Therefore f 0 (x4 ) ∈
{f 0 (a), f 0 (h), f 0 (n), f 0 (d), f 0 (f ), f 0 (k)}. Let f 0 (x4 ) = f 0 (d). The color of four edges in
S4 ∪ S5 incident to v8 are c0 + 1 and any three of f 0 (d), f 0 (e), f 0 (f ) and f 0 (k). But f 0 (e)
cannot be used there as f 0 (e) = c0 + 2; f 0 (d) cannot be used there as f 0 (x4 ) = f 0 (d).
Hence a new color must be introduced here resulting λ02,1 (T6 ) ≥ λ02,1 (G) ≥ 16. Similar
result holds when f 0 (x4 ) ∈ {f 0 (f ), f 0 (k)}. Now let us consider the case when f 0 (x4 ) ∈
{f 0 (a), f 0 (h), f 0 (n)}. Let us consider f 0 (x4 ) = f 0 (a). Here the colors of four edges in
S4 ∪S5 incident to v12 are c0 +1, f 0 (h), f 0 (n) and f 0 (o). Therefore f 0 (d), f 0 (f ) and f 0 (k)
must be used at three edges incident to v12 . As, f 0 (e) = c0 + 2 cannot be used at any
edge incident to v8 due to usage of c0 +1 at v8 , any one of f 0 (d), f 0 (f ) and f 0 (k) must be
used in x5 . But it is not possible as f 0 (d), f 0 (f ) and f 0 (k) are used in edges adjacent to
v12 . Hence another color must be introduced here resulting λ02,1 (T6 ) ≥ λ02,1 (G) ≥ 16.
Similar argument holds when f 0 (x4 ) ∈ {f 0 (h), f 0 (n)}. Hence the proof for this case.
Now we consider the case when f 0 (g) = c0 , f 0 (e) = c0 + 2 and c0 + 1 is used in
H. Let us consider a color c00 ∈ C = {0, 1, · · · , 15} \ {c0 , c0 + 1, c0 + 2} is unused
10 S. Bandopadhyay et al.
in H. Without loss of generality, say c00 = c0 + 5. For any other color c00 in C we can
prove the same result with similar arguments. From Lemma 4, c0 + 5 must be used
in 4 edges of S4 ∪ S5 in E(G) \ E(H). Here we assume c0 + 5 is used in 4 edges
adjacent to the vertices v1 , v3 , v8 and v12 respectively. Since f (g) = c0 , c0 ± 1 can
only be used in {c, i, j, m}. Let us consider f 0 (j) = c0 − 1. The three edges h, f and
i in Th are to be colored. Here we assume exactly two distinct pair of different types
of edges (p, q) and (r, s) are assigned consecutive colors such that p ∈ Th , q ∈ Ts
and r ∈ Th , s ∈ Tv . In that case c0 − 2, c0 − 3 and c0 − 4 must be assigned to edges
in Th in H. Let us consider f 0 (j) = c0 − 1. Now if f 0 (m) = c0 + 1, then two edges
j and m at 60◦ have colors c0 − 1 and c0 + 1 and from theorem 1, λ02,1 (T6 ) ≥ 16.
Again f 0 (i) 6= c0 + 1 as f 0 (e) = c0 + 2. Therefore f 0 (c) = c0 + 1. If f 0 (b) = c0 + 3,
then neither c0 + 4 nor c0 + 6 can be used at the edge a as c0 + 5 is used at an edge
incident to v1 . Hence f 0 (a) = c0 + 3. Similarly we can show that f 0 (d) = c0 + 4 and
f 0 (b) = c0 + 6. As c0 + 5 is used at an edge in S4 ∪ S5 incident to v12 , at least any
three among f 0 (a), f 0 (h), f 0 (n) and f 0 (o) must be assigned to the edges of S4 ∪ S5
incident to v10 . Note that f 0 (a) = c0 + 3 and f 0 (e) = c0 + 2. Therefore f 0 (a) cannot be
assigned to an edge incident to v10 . In that case f 0 (h) and f 0 (i) cannot be consecutive.
So we get f 0 (h) = c0 − 2, f 0 (f ) = c0 − 3 and f 0 (i) = c0 − 4. With similar argument
we can show that f 0 (o) = c0 − 5, f 0 (m) = c0 − 6, f 0 (k) = c0 − 7, f 0 (n) = c0 − 8 and
f 0 (l) = c0 −9. Now consider the edges of S4 ∪S5 incident to v8 . Only f 0 (d), f 0 (e), f 0 (f )
and f 0 (k) can be used at edges of S4 ∪ S5 incident to v8 . Note that f 0 (d) = c0 + 4
cannot be used there because c0 + 5 is used at an edge of S5 incident to v8 . Therefore
f 0 (k) = c0 −7, f 0 (f ) = c0 −3 and f 0 (e) = c0 +2 must be used at edges in S4 ∪S5 incident
to v8 . Now f 0 (x5 ) 6= f 0 (k) = c0 − 7 as f 0 (m) = c0 − 6. If f 0 (x5 ) = f 0 (f ) = c0 − 3,
then two edges j and x5 at 60◦ have colors c0 − 1 and c0 − 3 and from theorem 1,
λ02,1 (T6 ) ≥ 16. Hence f 0 (x5 ) = f 0 (e) = c0 + 2. Since either f 0 (y11 ) = c0 + 5 or
f 0 (y12 ) = c0 + 5 we get either f 0 (x6 ) = c0 − 3 or f 0 (x6 ) = c0 − 7. In both cases two
edges o and x6 residing at an angle 60◦ have colors (c0 − 5, c0 − 3) or (c0 − 5, c0 − 7).
Hence from theorem 1 λ02,1 (T6 ) ≥ 16. When more than two distinct pair of different
types of edges are assigned consecutive colors, arguing similarly, we can prove the same
result. Hence the proof.
Theorem 3. If two colors c0 and c0 + 2 have been assigned in any two adjacent edges
at an angle 180◦ in T6 , then λ02,1 (T6 ) ≥ 16.
Proof. Without loss of generality, assume f 0 (g) = c0 and f 0 (h) = c0 + 2 (Figure 2).
There may be two cases, when c0 + 1 is used in H and when c0 + 1 is not used in H.
First assume c0 + 1 is used in H. Let us consider a color c00 ∈ C = {0, 1, · · · , 15} \
{c0 , c0 + 1, c0 + 2} is unused in H and it is used at the edges of S4 ∪ S5 in E(G) \ E(H)
adjacent to v1 , v3 , v8 and v12 . Without loss of generality, say c00 = c0 + 7. For any other
color c00 in C we can prove the same result with similar arguments. Both the colors
c0 ± 1 must be used at edges in H incident to v9 . To make λ02,1 (G) less than 16, the
two colors must be used at two edges at 180◦ incident to v9 otherwise from theorem 1
or theorem 2, λ02,1 (T6 ) ≥ 16. So, we assume f 0 (j) = c0 + 1 and f 0 (i) = c0 − 1.
Similarly, f 0 (f ) = c0 − 2. The color c0 − 3 can be used at an edge adjacent to v5 . Let us
consider f 0 (n) = c0 − 3. Therefore, f 0 (m) = c0 − 4, f 0 (k) = c0 − 5, f 0 (o) = c0 − 6 and
L(2, 1)-edge labeling of Infinite Triangular Grid 11
f 0 (l) = c0 − 7. Similarly, it can be shown that f 0 (d) = c0 + 3, f 0 (c) = c0 + 4, f 0 (a) =
c0 + 5, f 0 (e) = c0 + 6 and f 0 (b) = c0 + 8. Now observe that f 0 (c), f 0 (m), f 0 (i) = c0 − 1
and f 0 (j) = c0 + 1 must be used at the edges at S4 ∪ S5 incident to v2 as the unused
color c00 is not used here. This implies f 0 (j) = c0 + 1 and f 0 (i) = c0 − 1 must be used
at two edges in S4 ∪ S5 incident to v2 which are at 180◦ , as otherwise from theorem 1
or theorem 2, λ02,1 (T6 ) ≥ 16. Hence c0 + 1 and c0 − 1 must be used at x8 and x9 . Now
notice that f 0 (d) = c0 + 3 and the edge d is at 60◦ and 120◦ with x9 and x8 respectively.
Hence at v2 , (c0 + 1, c0 + 3) must be used at two edges either at 60◦ or at 120◦ resulting
λ02,1 (T6 ) ≥ 16 from theorem 1 or theorem 2.
Now consider the case when f 0 (g) = c0 , f 0 (h) = c0 + 2 and c0 + 1 is not used in H.
Assume c0 +1 is used at four edges incident to v1 , v3 , v8 and v12 . Note that c0 −1 must be
used at an edge incident to v9 in H. Here we assume exactly two distinct pair of different
types of edges (p, q) and (r, s) are assigned consecutive colors such that p ∈ Th , q ∈ Ts
and r ∈ Th , s ∈ Tv . Consider f 0 (j) = c0 − 1. So, f 0 (f ) = c0 − 2 otherwise c0 and c0 − 2
must be at two adjacent edges at an angle 60◦ or 120◦ . Note that either f 0 (i) = c0 − 3 or
f 0 (i) = c0 + 3. First we assume f 0 (i) = c0 + 3. In that case c0 + 4 can only be used at an
edge incident to v6 in H, as otherwise c0 + 2 and c0 + 4 will be at two edges at an angle
60◦ or 120◦ . So, f 0 (d) = c0 + 4. Therefore, f 0 (a) = c0 + 5, f 0 (c) = c0 + 6, f 0 (e) = c0 + 7
and f 0 (b) = c0 +8. Similarly, f 0 (n) = c0 −3, f 0 (m) = c0 −4, f 0 (k) = c0 −5, f 0 (o) = c0 −6
and f 0 (l) = c0 − 7. Note that any three among f 0 (d), f 0 (e), f 0 (f ) and f 0 (k) must be used
at S4 ∪ S5 incident to v8 as c0 + 1 is used here. But f 0 (f ) = c0 − 2 and f 0 (k) = c0 − 5
cannot be used there as f 0 (j) = c0 − 1 and f 0 (o) = c0 − 6. Hence one more color must
be introduced here resulting λ02,1 (T6 ) ≥ λ02,1 (G) ≥ 16. Similar argument holds when
f 0 (i) = c0 − 3. Hence the proof.
Till now we have considered the case when in H, the unused color cu ∈
/ {5, 10}.
Now we consider the case when cu ∈ {5, 10} and the case when there is no unused
color in H.
Theorem 4. If a color cu ∈ {5, 10} is unused at H, then λ02,1 (T6 ) ≥ 16.
Proof. Without loss of generality let us assume color 5 is unused in H. The set of
colors {0, 1, · · · , 4} must be used in same type of edges and same holds for the sets
{6, 7, · · · , 10} and {11, 12, · · · , 15} otherwise there exists at least two disjoint pair of
edges (p, q) and (r, s) where consecutive colors are used in each pair and there we can
prove λ02,1 (T6 ) ≥ 16 using similar argument as depicted in Lemma 6 and Theorem 1 or
2 or 3. Let us consider p = f, q = a, f 0 (p) = c0 and f 0 (q) = c0 + 1. From Observation
6, c0 cannot be used in the subgraph H 0 isomorphic to H centering S10 = {v1 , v2 , v5 }.
If c0 6= 10, then from Theorem 1 or 2 or 3 λ02,1 (T6 ) ≥ 16. If c0 = 10 then f 0 (q) =
c0 + 1 = 11. In that case the colors {0, 1, · · · , 4} must be used in Tv , {6, 7, · · · , 10}
must be used in Th and {11, 12, · · · , 15} must be used in Ts . From Observation 4, the
edges for reusing f 0 (f ) = c0 = 10 are y5 , y12 , y16 and (u3 , u4 ). If f 0 (f ) = c0 = 10
is used at (u3 , u4 ), then f 0 (a) = c0 + 1 = 11 cannot be used at its opposite edge y21
and hence from Observation 4, Lemma 6 and Theorem 1 or 2 or 3 λ02,1 (T6 ) ≥ 16. If
f 0 (f ) = c0 = 10 is not used at (u3 , u4 ), then either color 5 or a color c00 6= {5, 10} used
in H must be used there. If a color c00 is used there, then there exists a pair of opposite
edges where c00 cannot be used and again from Observation 4, Lemma 6 and Theorem 1
12 S. Bandopadhyay et al.
or 2 or 3 λ02,1 (T6 ) ≥ 16. So, to keep λ02,1 (T6 ) below 16, color 5 must be used at
(u3 , u4 ). With exactly same argument we can show that color 5 must also be used at
y5 , y12 , y16 otherwise λ02,1 (T6 ) ≥ 16. Remember that the color 4 is used in Tv and it
must also be used at its opposite edges. Note that for any edges e1 ∈ Tv \ {m}, either
e1 or its opposite edge is adjacent to an edge e2 where f (e2 ) = 5. Hence f 0 (m) = 4.
But y13 , the opposite edge of m, cannot have color 4 as color 5 is used at y12 . Hence
from Observation 4, Lemma 6 and Theorem 1 or 2 or 3 λ02,1 (T6 ) ≥ 16.
Theorem 5. If all colors c1 ∈ {0, · · · , 14} are used at H, then λ02,1 (T6 ) ≥ 16.
Proof. In this case there exists a pair of different types of edges in H where (c0 , c0 + 1)
are used. From Observation 6, there exists a H 0 isomorphic to H where c0 or c0 + 1
cannot be used. Hence either from Theorem 4 or from Lemma 6 and Theorem 1 or 2
or 3, it follows that λ02,1 (T6 ) ≥ 16.
3 Result for circular-L(2, 1)-edge labeling
0
Lemma 7. σ2,1 (T6 ) ≤ 18
17
13 15 12 14 16 13
8 0 7 1 6 2 10 3 9 4 8 0 7
12 14 16 13 15 12
10 1 9 2 8 3 7 4 6 0 10 1 9
16 13 15 12 14 16
7 2 6 3 10 4 9 0 8 1 7 2 6
15 12 14 16 13 15
9 3 8 4 7 0 6 1 10 2 9 3 8
14 16 13 15 12 14
6 4 10 0 9 1 8 2 7 3 6 4 10
13 15 12 14 16 13
8 0 7 1 6 2 10 3 9 4 8 0 7
12 14 16 13 15 12
17
Fig. 3: Circular L(2, 1)-edge labeling of T6
Proof. In this grid there are three types of edges- horizontal, vertical and slanted. In
order to proof the Lemma, we now consider the labeling shown in Figure 3. Assuming
left bottom corner point as origin, the labeling functions corresponding to horizontal,
vertical and slanted edges can be stated as:
f 0 ((x, y), (x + 1, y)) = (7x + y) mod 5 + 12
f 0 ((x, y), (x, y + 1)) = (3y − x + 2) mod 5 + 6
f 0 ((x − 1, y + 1), (x, y)) = (x + 4y − 1) mod 5
L(2, 1)-edge labeling of Infinite Triangular Grid 13
. Observe that different types of edges get different colors in the coloring. Horizontal
edges get color 12, 13, 14, 15, 16; vertical edges get 6, 7, 8, 9, 10 and slanted edges get
0, 1, 2, 3, 4. By the pattern it is clear that two adjacent edges of same type do not get
two consecutive colors. By the definition of n-circular-L(2, 1)-edge labeling 0 and n
are two consecutive colors. In our coloring there are many places where two adjacent
edges get 0 and 16. So, the color 16 cannot be the circular span of the grid. That’s why
we introduce a new color 17, which is used at edges as a replacement for 16 such that
0 and 16 become two non-consecutive colors. Two such 16 colored edges are shown
in Figure 3 whose colors can be replaced by 17. Putting 17 at any one such edge is
sufficient. The main goal behind introducing a new color 17 was to make 0 and 16
non-consecutive. As the colors 5 and 11 are unused in the graph, we can conclude that
no two adjacent edges of different types get two consecutive colors. Now we have to
show that no two edges at distance two get the same color. For the same type of edges it
can be easily followed from the pattern of repetition. In case of different type of edges,
observe that distant two edges of two different types get color with difference at least
two. Hence this labeling can be extended to infinite grid.
4 Conclusion
Here we prove the conjecture λ02,1 (T6 ) = 16 given by Lin and Wu [3]. We prove that
λ02,1 (T6 ) ≥ 16 and as λ02,1 (T6 ) ≤ 16 [3], it immediately follows that λ02,1 (T6 ) = 16.
0
We also show that σ2,1 (T6 ) ≤ 18 by giving a labeling function. Determining the value
0
of σ2,1 (T6 ) is an open problem and can be done as a future work.
References
1. W. K. Hale, Frequency assignment: Theory and applications, Proceedings of the IEEE 68
(12) (1980) 1497-1514. doi:10.1109/PROC.1980.11899.
2. F. Roberts, Working group agenda, In: DIMACS/DIMATIA/Renyi Working Group on Graph
Colorings and their Generalizations (2003).
3. W. Lin, J. Wu, Distance two edge labelings of lattices, J. Comb. Optim. 25 (4) (2013) 661-
679. doi:10.1007/ s10878-012-9508-5.
4. Q. Chen, W. Lin, L(j, k)-labelings and L(j, k)-edge-labelings of graphs, Ars Comb. 106
(2012) 161-172.
5. D. He, W. Lin, L(1, 2)-edge-labelings for lattices, Applied Mathematics-A Journal of Chi-
nese Universities 29 (2014) 230-240. doi:10.1007/s11766-014-3176-4.
6. T. Calamoneri, Optimal L(j, k)-edge-labeling of regular grids, Int. J. Found. Comput. Sci.
26 (4) (2015) 523-535. doi:10.1142/S012905411550029X.
7. T. Calamoneri, The L(h, k)-labelling problem: An updated survey and annotated bibliogra-
phy, Comput. J. 54 (8) (2011) 1344-1371. doi:10.1093/comjnl/bxr037.
8. J. R. Griggs, X. T. Jin, Real number labelings for paths and cycles, Internet Mathematics 4
(1) (2007) 65-86. doi:10.1080/15427951.2007.10129140.
9. J. R. Griggs, R. K. Yeh, Labelling graphs with a condition at distance 2, SIAM J. Discrete
Math. 5 (4) (1992) 586-595. doi:10.1137/0405048.
10. S. Bandopadhyay, S. C. Ghosh, S. Koley, Improved bounds on the span of L(1, 2)-edge
labeling of some infinite regular grids, in: 18th Cologne-Twente Workshop on Graphs and
Combinatorial Optimization (CTW 2020), Springer, accepted, September 14-16, 2020.
14 S. Bandopadhyay et al.
11. J. van den Heuvel, R. A. Leese, M. A. Shepherd, Graph labeling and radio channel assign-
ment, Journal of Graph Theory 29 (4)(1998) 263-283.
12. D. D, J. V. Kureethara, On L(2,1)-edge coloring number of regular grids, An. St Univ. Ovid-
ius Constanta 27 (3) (2019) 65-81. doi:10.2478/auom-2019-0034.