# Improved Bounds on the Span of $L(1,2)$-edge Labeling of Some Infinite
Regular Grids111Preliminary version of this paper was presented at the 18th
Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2020),
September 14-16, 2020 Bandopadhyay et al. (2020)

Susobhan Bandopadhyay1  Sasthi C. Ghosh2  Subhasis Koley2  School of Computer
Sciences, National Institute of Science Education and Research, Bhubaneswar,
India
Advanced Computing and Microelectronics Unit, Indian Statistical Institute,
Kolkata, India

###### Abstract

For two given nonnegative integers $h$ and $k$, an $L(h,k)$-edge labeling of a
graph $G$ is the assignment of labels $\\{0,1,\cdots,n\\}$ to the edges so
that two edges having a common vertex are labeled with difference at least $h$
and two edges not having any common vertex but having a common edge connecting
them are labeled with difference at least $k$. The span
$\lambda^{\prime}_{h,k}{(G)}$ is the minimum $n$ such that $G$ admits an
$L(h,k)$-edge labeling. Here our main focus is on finding
$\lambda^{\prime}_{1,2}{(G)}$ for $L(1,2)$-edge labeling of infinite regular
hexagonal ($T_{3}$), square ($T_{4}$), triangular ($T_{6}$) and octagonal
($T_{8}$) grids. It was known that $7\leq\lambda^{\prime}_{1,2}{(T_{3})}\leq
8$, $10\leq\lambda^{\prime}_{1,2}{(T_{4})}\leq 11$,
$16\leq\lambda^{\prime}_{1,2}{(T_{6})}\leq 20$ and
$25\leq\lambda^{\prime}_{1,2}{(T_{8})}\leq 28$. Here we settle two long
standing open questions i.e. $\lambda^{\prime}_{1,2}{(T_{3})}$ and
$\lambda^{\prime}_{1,2}{(T_{4})}$. We show
$\lambda^{\prime}_{1,2}{(T_{3})}=7$, $\lambda^{\prime}_{1,2}{(T_{4})}=11$. We
also improve the bound for $T_{6}$ and $T_{8}$ and prove
$\lambda^{\prime}_{1,2}{(T_{6})}\geq 18$, $\lambda^{\prime}_{1,2}{(T_{8})}\geq
26$.

###### keywords:

Channel assignment problem, $L(1,2)$-labeling, infinite grids, lower bound,
upper bound.

##  1 Introduction

Channel assignment problem (CAP) is one of the fundamental problems in
wireless communication where frequency channels are assigned to transmitters
such that interference can not occur. The objective of the CAP is to minimize
the span of frequency spectrum. In 1980, Hale Hale (1980) first formulated the
CAP as a classical vertex coloring problem. Later on, in 1988 Roberts Roberts
(2003) introduced $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
$\mathbf{f}:V\xrightarrow{}\\{0,1,\cdots,n\\},\forall v\in V$ such that
$|\mathbf{f}(u)-\mathbf{f}(v)|\geq h$ when $d(u,v)=1$ and
$|\mathbf{f}(u)-\mathbf{f}(v)|\geq k$ when $d(u,v)=2$. Here, distance between
vertices $u$ and $v$, $d(u,v)$ is $k^{\prime}$ if at least $k^{\prime}$ edges
are required to connect $u$ and $v$.

The span $\lambda_{h,k}(G)$ of $L(h,k)$-vertex labeling is the minimum $n$
such that $G$ admits an $L(h,k)$-vertex labeling. In 1992 Griggs and Yeh
Griggs and Yeh (1992) extended the concept by introducing
$L(k_{1},k_{2},\cdots,k_{l})$-vertex labeling with separation
$\\{k_{1},k_{2},\cdots,k_{l}\\}$ for $\\{1,2,\cdots,l\\}$ distant vertices and
their main focus was on $L(h,k)$-vertex labeling for a special case $h=2,\
k=1$. In 2007, Griggs and Jin Griggs and Jin (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
$\mathbf{f}:E\xrightarrow{}\\{0,1,\cdots,n\\},\forall e\in E$ such that
$|\mathbf{f}(e_{1})-\mathbf{f}(e_{2})|\geq h$ when $d(e_{1},e_{2})=1$ and
$|\mathbf{f}(e_{1})-\mathbf{f}(e_{2})|\geq k$ when $d(e_{1},e_{2})=2$. Here,
for any two edges $e_{1}$ and $e_{2}$, the distance $d(e_{1},e_{1})$ is
$k^{\prime}$ if at least $(k^{\prime}-1)$ edges are required to connect
$e_{1}$ and $e_{2}$.

Like $L(h,k)$-vertex labeling, the span $\lambda^{\prime}_{h,k}(G)$ of
$L(h,k)$-edge labeling is the minimum $n$ such that $G$ admits an
$L(h,k)$-edge labeling. In 2011, Calamoneri did a rigorous survey Calamoneri
(2011) on both vertex and edge labeling problems. Authors in Lin and Wu
(2013); Chen and Lin (2012); He and Lin (2014); Calamoneri (2015) have studied
$L(h,k)$-edge labeling of regular infinite hexagonal ($T_{3}$), square
($T_{4}$), triangular ($T_{6}$) and octagonal ($T_{8}$) grids for the special
case of $h=1$ and $k=2$. They obtained some upper and lower bounds on
$\lambda^{\prime}_{1,2}(G)$ for $T_{3}$, $T_{4}$, $T_{6}$ and $T_{8}$ with a
gap between them. In this paper, we improved some of these gaps.

Given a graph $G(V,E)$, its line graph $L(G)(V^{\prime},E^{\prime})$ is a
graph such that each vertex of $L(G)$ represents an edge of $G$ and two
vertices of $L(G)$ have an edge if and only if their corresponding edges share
a common vertex in $G$. It is known that if $G$ is $d$-regular then $L(G)$ is
$2(d-1)$-regular. Fig. 1 shows $T_{3}$, $L(T_{3})$, $L(T_{4})$, $T_{6}$ and
$T_{8}$. Note that edge labeling of $G$ is equivalent to vertex labeling of
$L(G)$. In our approach, instead of $L(1,2)$-edge labeling of $T_{3}$ and
$T_{4}$, we use $L(1,2)$-vertex labeling of $L(T_{3})$ and $L(T_{4})$. Note
that, $L(T_{6})$ and $L(T_{8})$ are $10$-regular and $14$-regular,
respectively. Because of this high degree, we consider $L(1,2)$-edge labeling
of $T_{6}$ and $T_{8}$ directly. Our results on $\lambda^{\prime}_{1,2}(G)$
for $T_{3}$, $T_{4}$, $T_{6}$, $T_{8}$ are stated in Table 1. In this table,
$a-b$ represents that $a\leq\lambda^{\prime}_{1,2}(G)\leq b$. Here, we use
coloring and labeling interchangeably.

Figure 1: $T_{3}$, $L(T_{3})$, $L(T_{4})$, $T_{6}$ and $T_{8}$. Table 1: The main results. | $\lambda^{\prime}_{1,2}(G)$
---|---
Grid | $T_{3}$ | $T_{4}$ | $T_{6}$ | $T_{8}$
Known |  7-8 He and Lin (2014) |  10-11 He and Lin (2014) |  16-20 Calamoneri (2015) |  25-28 Calamoneri (2015)
Ours | 7 | 11 | 18-20 | 26-28

##  2 Results

Figure 2: Sub graph $G_{S}$ of $L(T_{3})$

###  2.1 Hexagonal grid

Consider $L(T_{3})$ and the three co-ordinate axes $\mathbf{X},\mathbf{Y}$ and
$\mathbf{Z}$ as shown in Figure 2. Each vertex is an intersection of two of
the three axes. The vertices of $L(T_{3})$ can be partitioned into three
disjoint sets $U_{xy},V_{yz}$ and $W_{zx}$ as defined bellow:
$U_{xy}=\\{u_{xy}:u_{xy}\ is\ an\ intersection\ of\ \mathbf{X=x}\ and\
\mathbf{Y=y}\\},\\\ V_{yz}=\\{v_{yz}:v_{yz}\ is\ an\ intersection\ of\
\mathbf{Y=y}\ and\ \mathbf{Z=z}\\},\\\ W_{zx}=\\{w_{zx}:w_{zx}\ is\ an\
intersection\ of\ \mathbf{Z=z}\ and\ \mathbf{X=x}\\}.\\\ $

###### Theorem 1

222Proof of this theorem is modified from that of the conference version
Bandopadhyay et al. (2020).

$\lambda^{\prime}_{1,2}(T_{3})=7$.

######  Proof 2.2.

The coloring functions of vertices of $L(T_{3})$ are defined as follows.
$f(u_{xy})=\left(\left(4\times\lceil\frac{x}{2}\rceil+2\times\lfloor\frac{x}{2}\rfloor\right)\mod
8+\left(5\times y\right)\mod 8\right)\mod 8,\forall u_{xy}\in U_{xy}.$
$g(v_{yz})=\left(\left(2+3\times z\right)\mod 8+\left(2\times y\right)\mod
8\right)\mod 8,\forall v_{yz}\in V_{yz}.$
$h(w_{zx})=\left(\left(1+5\times z\right)\mod 8+\left(2\times x\right)\mod
8\right)\mod 8,\forall w_{zx}\in W_{zx}.$

Here we consider that $0\leq(x\mod y)<y$ where $x\in\mathbb{Z}$ and
$y\in\mathbb{Z}\setminus\\{0\\}$.

The colors of the vertices of a finite subgraph $G_{S}$ of $L(T_{3})$ are
shown in Figure 2. It can be verified that colors of every pair of vertices
satisfy all the $L(1,2)$-vertex labeling constraints. It is also evident that
the colors obey a regular modulo pattern which can be extended up to infinity
and there will be no color conflict between any pair of vertices of $L(T_{3})$
if the assigned colors satisfy the coloring functions. The minimum and maximum
color used here are $0$ and $7$ respectively. Hence
$\lambda_{1,2}(L(T_{3}))\leq 7$. It has been shown in He and Lin (2014) that
$\lambda_{1,2}(L(T_{3}))\geq 7$. Hence
$\lambda^{\prime}_{1,2}(T_{3})=\lambda_{1,2}(L(T_{3}))=7$.

###  2.2 Square grid

Let us consider the induced subgraph $G$ of $L(T_{4})$ as shown in Fig 3 where
all vertices are at mutual distance at most three. Let $S_{1}=\\{a,b\\}$,
$S_{2}=\\{k,l\\}$, $S_{3}=\\{c,g\\}$, $S_{4}=\\{f,j\\}$ and $S_{5}=\\{d,\ e,\
h,\ i\\}$.

######  Definition 2.3.

The set of vertices in $S_{5}$ are termed as central vertices in $G$.

######  Definition 2.4.

The set of vertices in $S_{1}\cup S_{2}\cup S_{3}\cup S_{4}$ are termed as
peripheral vertices in $G$.

Now we have the following observations in $G$. Here the color of vertex $a$ is
denoted by $\mathbf{f}(a)$.

Figure 3: Sub graph $G$ of $L(T_{4})$

###### Observation 1

: If colors of vertices of $G$ are all distinct then $\lambda_{1,2}(G)\geq
11$.

######  Proof 2.5.

As $G$ has $12$ vertices, if all of them get distinct colors then
$\lambda_{1,2}(G)\geq 11$.

###### Observation 2

: No color can be used thrice in $G$. Colors used at the central vertices in
$S_{5}$ can not be reused in $G$. Colors used at the peripheral vertices in
$S_{1}$ can be reused only at the peripheral vertices in $S_{2}$. Similarly,
colors used at the peripheral vertices in $S_{3}$ can be reused only at the
peripheral vertices in $S_{4}$.

######  Proof 2.6.

No three vertices are mutually distant three apart. Hence no color can be used
thrice in $G$. For any central vertex in $S_{5}$ there does not exist any
vertex in $G$ which is distance three apart from it. So colors used in the
central vertices in $S_{5}$ can not be reused in $G$. For all peripheral
vertices in $S_{1}\cup S_{2}$, $d(x,y)=3$ only when $x\in S_{1}$ and $y\in
S_{2}$. Hence color used at peripheral vertex in $S_{1}$ can only be reused in
$S_{2}$. Similarly, color used at peripheral vertex in $S_{3}$ can only be
reused in $S_{4}$.

###### Observation 3

: If $\mathbf{f}(x)=\mathbf{f}(y)=\mathbf{c}$ where $x\in S_{1}$ and $y\in
S_{2}$ then either $\mathbf{c}\pm 1$ is to be used in $(S_{1}\cup
S_{2})\setminus\\{x,y\\}$ or it should remain unused in $G$. Similarly, if
$\mathbf{f}(x)=\mathbf{f}(y)=\mathbf{c}$ where $x\in S_{3}$ and $y\in S_{4}$
then either $\mathbf{c}\pm 1$ is to be used in $(S_{3}\cup
S_{4})\setminus\\{x,y\\}$ or it should remain unused in $G$.

######  Proof 2.7.

Note that for all vertices $z\in V(G)\setminus(S_{1}\cup S_{2})$, either
$d(z,x)=2$ or $d(z,y)=2$, where $x\in S_{1}$ and $y\in S_{2}$. Hence
$\mathbf{c}\pm 1$ can not be used in $V(G)\setminus(S_{1}\cup S_{2})$. So
$\mathbf{c}\pm 1$ can only be used in $(S_{1}\cup S_{2})\setminus\\{x,y\\}$ or
it should remain unused in $G$. Similarly, if
$\mathbf{f}(x)=\mathbf{f}(y)=\mathbf{c}$, where $x\in S_{3}$ and $y\in S_{4}$,
then $\mathbf{c}\pm 1$ can only be used in $(S_{3}\cup
S_{4})\setminus\\{x,y\\}$ or it should remain unused in $G$.

###### Observation 4

: Let $\mathbf{f}(x)=\mathbf{f}(y)=\mathbf{c}$ where $x\in S_{1}$ and $y\in
S_{2}$. If $|\mathbf{f}(x)-\mathbf{f}(x^{\prime})|\geq 2$, where
$x^{\prime}\in S_{1}\setminus\\{x\\}$, then one of $\mathbf{c}\pm 1$ must
remain unused in $G$. Similarly if $|\mathbf{f}(y)-\mathbf{f}(y^{\prime})|\geq
2$, where $y^{\prime}\in S_{2}\setminus\\{y\\}$, then one of $\mathbf{c}\pm 1$
must remain unused in $G$. Similar facts hold when $x\in S_{3}$,
$x^{\prime}\in S_{3}\setminus\\{x\\}$, $y\in S_{4}$ and $y^{\prime}\in
S_{4}\setminus\\{y\\}$.

######  Proof 2.8.

Since $|\mathbf{f}(x)-\mathbf{f}(x^{\prime})|\geq 2$,
$\mathbf{f}(x^{\prime})\neq\mathbf{c}\pm 1$. Hence from observation 3, one of
$\mathbf{c}\pm 1$ must remain unused in $G$.

If no color is reused in $G$, then $\lambda_{1,2}(G)\geq 11$ from observation
1. To make $\lambda_{1,2}(G)<11$, at least one color must be reused in $G$.
From observation 2, there are at most $4$ distinct pairs of peripheral
vertices in $G$ where a pair can have the same color. Now consider the
subgraph $G_{1}$ of $L(T_{4})$ as shown in Fig. 4.a. Note that $G_{1}$
consists of $5$ subgraphs $G^{\prime}$, $G^{\prime}_{1}$, $G^{\prime}_{2}$,
$G^{\prime}_{3}$ and $G^{\prime}_{4}$ which all are isomorphic to $G$ having
central vertices $\\{d,h,i,e\\}$, $\\{t_{1},c,d,a\\}$, $\\{b,e,f,t_{2}\\}$,
$\\{i,l,t_{3},j\\}$ and $\\{g,t_{4},k,h\\}$ respectively. Based on the span
requirements of coloring $G_{1}$, we derive the following theorem.

Figure 4: Different coloring of subgraph $G_{1}$.

######  Theorem 2.9.

$\lambda_{1,2}(L(T_{4}))=\lambda_{1,2}(G_{1})=11$.

######  Proof 2.10.

Due to He and Lin He and Lin (2014), it is already known that
$\lambda_{1,2}(L(T_{4}))\leq 11$. Thus in this section our main goal will be
to improve the lower bound and show $\lambda_{1,2}(L(T_{4}))\geq 11$. We do
some case analysis depending on how the peripheral vertices are colored.
Case 1: When at most one pair of peripheral vertices use the same color in any
sub graph of $L(T_{4})$ isomorphic to $G$.
If no color is reused in $G^{\prime}$, then $\lambda_{1,2}(G^{\prime})\geq 11$
from observation 1. We now consider the case when exactly one pair reuse a
color in $G^{\prime}$. Without loss of generality, consider
$\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$. From Observation 3, $c_{1}\pm 1$ can only
be put in $\\{b,k\\}$. Let $\mathbf{f}(k)=c_{1}-1$ and
$\mathbf{f}(b)=c_{1}+1$. We assume that $c_{1}-1$ is the minimum color. Let us
consider $\mathbf{f}(d)=c_{1}+n$ where $n\in\mathbb{N}$ and $n\geq 2$. From
observation 4, $x\in\\{c_{1},c_{1}+n\\}$ can be reused in $G^{\prime}_{2}$
only if one of $x\pm 1$ remains unused in $G^{\prime}_{2}$. In either case,
$\lambda_{1,2}(G^{\prime}_{2})\geq 11$. So $x$ can not be reused in
$G^{\prime}_{2}$. Since $\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$, $c_{1}-1$ can
only be put in $\\{r_{2},s_{2}\\}$ as vertex $b$ is already colored and for
all other vertices $z\in V(G^{\prime}_{2})\setminus\\{r_{2},s_{2}\\}$, either
$d(z,a)=2$ or $d(z,l)=2$. Without loss of generality, let
$\mathbf{f}(r_{2})=c_{1}-1$. In that case, $c_{1}+n\pm 1$ can only be put in
$\\{e,s_{2}\\}$. Without loss of generality, let $\mathbf{f}(e)=c_{1}+n-1$ and
$\mathbf{f}(s_{2})=c_{1}+n+1$. Since $\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$,
$\mathbf{f}(i)\neq c_{1}\pm 1$ and hence $|\mathbf{f}(l)-\mathbf{f}(i)|\geq
2$. Now if $|\mathbf{f}(d)-\mathbf{f}(c)|\geq 2$, then from observation 4, one
of $\mathbf{f}(c)\pm 1$, $\mathbf{f}(d)\pm 1$ and $\mathbf{f}(i)\pm 1$ remains
unused in $G^{\prime}_{4}$ if $\mathbf{f}(c)$ or $\mathbf{f}(d)$ or
$\mathbf{f}(i)$ is reused in $G^{\prime}_{4}$ respectively. In either case,
this implies $\lambda_{1,2}(G^{\prime}_{4})\geq 11$. So
$|\mathbf{f}(d)-\mathbf{f}(c)|=1$ and $\mathbf{f}(c)=c_{1}+n+1$. There are $5$
more vertices $\\{g,h,i,j,f\\}$ in $G^{\prime}$ which are to be colored with
$5$ distinct colors. Hence at least color $c_{1}+n+6$ must be used. Observe
that if $\mathbf{f}(f)=c_{1}+n+2$ then $|\mathbf{f}(e)-\mathbf{f}(f)|=3$ and
$|\mathbf{f}(k)-\mathbf{f}(h)|\geq 3$ implying
$\lambda_{1,2}(G^{\prime}_{3})\geq 11$ from observation 4. As
$d(s_{2},i)=d(s_{2},j)=2$ and $\mathbf{f}(s_{2})=c_{1}+n+1$, we get
$\mathbf{f}(i)\neq c_{1}+n+2$ and $\mathbf{f}(j)\neq c_{1}+n+2$. Therefore,
either $\mathbf{f}(g)=c_{1}+n+2$ or $\mathbf{f}(h)=c_{1}+n+2$. So,
$\mathbf{f}(p_{4})\neq c_{1}+n+1$ and $\mathbf{f}(q_{4})\neq c_{1}+n+1$. In
that case, $\mathbf{f}(p_{4})$ and $\mathbf{f}(q_{4})$ must be in
$\\{c_{1}+n,c_{1}+n-1\\}$ if color $c_{1}+n$ is to be reused in
$G^{\prime}_{4}$, otherwise, $\lambda_{1,2}(G_{1})\geq 11$. As $c_{1}$ can not
be reused in $G^{\prime}_{4}$, either $\mathbf{f}(r_{4})=c_{1}+1$ or
$\mathbf{f}(s_{4})=c_{1}+1$. Let $\mathbf{f}(r_{4})=c_{1}+1$. When $n=2$,
$c_{1}+n-1=c_{1}+1$ and when $n=3$, $c_{1}+n-1=c_{1}+2$. As
$d(p_{4},l)=d(p_{4},r_{4})=d(q_{4},l)=d(q_{4},r_{4})=2$,
$\mathbf{f}(p_{4}),\mathbf{f}(q_{4})\notin\\{c_{1}+1,c_{1}+2\\}$. So, $n\geq
4$ and hence $c_{1}+n+6\geq c_{1}+10$. So at least $12$ color are required in
$G_{1}$ including $c_{1}-1$ and $c_{1}+10$. Hence $\lambda_{1,2}(G_{2})\geq
11$.

Case 2: There exists at least one subgraph of $L(T_{4})$ isomorphic to $G$
where two pairs of peripheral vertices use a color each.
There are two different ways of reusing two colors in $G^{\prime}$.
Case 2.1: First consider the case when $\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$ and
$\mathbf{f}(c)=\mathbf{f}(j)=c_{2}$. From observation 3, $c_{1}\pm 1$ and
$c_{2}\pm 1$ must be used in $\\{b,k\\}$ and $\\{g,f\\}$ respectively. From
observation 2, $c_{1}$ can only be reused in $\\{r_{2},s_{2}\\}$ in
$G^{\prime}_{2}$. But $\mathbf{f}(r_{2})\neq c_{1}$ and $\mathbf{f}(s_{2})\neq
c_{1}$ as $|\mathbf{f}(b)-c_{1}|=1$ and $d(b,r_{2})=d(b,s_{2})=2$. Again, from
observation 2, $c_{2}$ can only be reused in $\\{p_{2},q_{2}\\}$. But
$\mathbf{f}(p_{2})\neq c_{2}$ and $\mathbf{f}(q_{2})\neq c_{2}$ as
$|\mathbf{f}(f)-c_{2}|=1$ and $d(f,p_{2})=d(f,q_{2})=2$. From observation 3,
if $\mathbf{f}(i)$ is to be reused in $G^{\prime}_{2}$, then
$|\mathbf{f}(i)-c_{2}|=1$. But $\mathbf{f}(i)\neq c_{2}\pm 1$ as $d(c,i)=2$
and $\mathbf{f}(c)=c_{2}$. If $\mathbf{f}(d)$ is to be reused in
$G^{\prime}_{2}$, then $|\mathbf{f}(d)-c_{1}|=1$. But $\mathbf{f}(d)\neq
c_{1}\pm 1$ as $d(d,l)=2$ and $\mathbf{f}(l)=c_{1}$. Therefore, no color can
be reused in $G^{\prime}_{2}$ and hence $\lambda_{1,2}(G_{1})\geq 11$.

Case 2.2: Consider the case when $\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$ and
$\mathbf{f}(b)=\mathbf{f}(k)=c_{2}$. Without loss of generality, assume
$c_{2}>c_{1}$. From observation 3, $c_{1}\pm 1$ and $c_{2}\pm 1$ must be used
in $\\{b,k\\}$ and $\\{a,l\\}$ respectively. Even if we set $c_{2}=c_{1}+1$,
at least one of $c_{1}-1$ and $c_{2}+1$ must remain unused in $G^{\prime}$. So
the $8$ vertices in $V(G^{\prime})\setminus(\\{a,l\\}\cup\\{b,k\\})$ must get
$8$ distinct colors other than $c_{1}$ and $c_{2}$. So,
$\lambda_{1,2}(G^{\prime})\geq 10$. Note that $\lambda_{1,2}(G^{\prime})=10$
only if $c_{2}=c_{1}+1$, $c_{1}$ is minimum color ($c_{1}-1$ does not exists)
or $c_{2}$ is maximum color ($c_{2}+1$ does not exists). If both $c_{1}$ and
$c_{2}$ are non-extreme color, then $\lambda_{1,2}(G^{\prime})\geq 11$ and we
are done. So, we consider $c_{1}=0$, $c_{2}=c_{1}+1=1$ and $c_{2}+1=2$ as
unused in $G^{\prime}$. In that case, $\mathbf{f}(d)=x\geq 3$ and hence
$|\mathbf{f}(d)-\mathbf{f}(a)|\geq 3$. From observation 4, if $x$ is reused in
$G^{\prime}_{2}$, then one of $x\pm 1$ can not be used in $G^{\prime}_{2}$. If
only $x$ is reused in $G^{\prime}_{2}$, then
$\lambda_{1,2}(G^{\prime}_{2})\geq 11$. If $x$ and one of
$\\{\mathbf{f}(i),\mathbf{f}(j)\\}$ are reused in $G^{\prime}_{2}$, then from
Case 2.1 above, $\lambda_{1,2}(G_{1})\geq 11$. If $x$ and both of
$\\{\mathbf{f}(i),\mathbf{f}(j)\\}$ are reused in $G^{\prime}_{2}$, from Case
3 below, we will see that $\lambda_{1,2}(G_{1})\geq 11$. So, to keep
$\lambda_{1,2}(G_{1})<11$, $x$ should not be reused in $G^{\prime}_{2}$. In
that case, $x-1$ must be used at one of $\\{c,g,h,e\\}$ in $G^{\prime}$. Now
arguing similarly as stated in case $\mathbf{1}$, we can conclude that $x+7$
must be used in $G^{\prime}_{1}$ or $G^{\prime}_{2}$. If $x=3$, then $x-1=2$
must be used in $G^{\prime}$ which is a contradiction, as $2$ must remain
unused in $G^{\prime}$. Hence $x\geq 4$ implying $x+7=11$. Hence
$\lambda_{1,2}(G_{1})\geq 11$.

Case 3: The exists at least one sub graph of $L(T_{4})$ isomorphic to $G$
where three pairs of peripheral vertices use a color each.
Without loss of generality, let us consider
$\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$, $\mathbf{f}(b)=\mathbf{f}(k)=c_{2}$ and
$\mathbf{f}(c)=\mathbf{f}(j)=c_{3}$. From observation 3, $c_{1}\pm 1$ and
$c_{2}\pm 1$ must be used in $\\{b,k\\}$ and $\\{a,l\\}$ respectively. It can
be observed that $\lambda_{1,2}(G^{\prime})=9$ only if $|c_{1}-c_{2}|=1$,
$|c_{3}-\mathbf{f}(g)|=1$, $|c_{3}-\mathbf{f}(f)|=1$ and any one of
$\\{c_{1},c_{2}\\}$ is one extreme color. Without loss of generality consider
$\mathbf{f}(g)=c_{3}+1$, $\mathbf{f}(f)=c_{3}-1$, $c_{1}$ is minimum color and
$c_{2}=c_{1}+1$. From observation 2, $c_{3}$ can only be reused in
$\\{p_{2},q_{2}\\}$. But $\mathbf{f}(p_{2})\neq c_{3}$ and
$\mathbf{f}(q_{2})\neq c_{3}$ as $\mathbf{f}(f)=c_{3}-1$ and
$d(f,p_{2})=d(f,q_{2})=2$. From observation 3, if $\mathbf{f}(i)$ is to be
reused in $G^{\prime}_{2}$, then $|\mathbf{f}(i)-c_{3}|=1$. But
$\mathbf{f}(i)\neq c_{3}\pm 1$ as $d(c,i)=2$ and $\mathbf{f}(c)=c_{3}$. From
observation 2, $c_{1}$ can only be reused in $\\{r_{2},s_{2}\\}$. But
$\mathbf{f}(r_{2})\neq c_{1}$ and $\mathbf{f}(s_{2})\neq c_{1}$ as
$\mathbf{f}(b)=c_{2}=c_{1}+1$ and $d(b,r_{2})=d(b,s_{2})=2$. Now arguing
similarly as stated in case $\mathbf{2.2}$ above, we can conclude that
$c_{2}+1$ must remain unused in $G^{\prime}$. So, $(c_{1}-\mathbf{f}(d))\geq
3$. Now from observation 4, if $\mathbf{f}(d)$ is reused in $G^{\prime}_{2}$
then any one of $\mathbf{f}(d)\pm 1$ must remain unused in $G^{\prime}_{2}$.
Thus in $G^{\prime}_{2}$, only $\mathbf{f}(d)$ can be reused by keeping one of
$\mathbf{f}(d)\pm 1$ as unused. Hence $\lambda_{1,2}(G_{1})\geq 11$. If we
consider $\lambda_{1,2}(G^{\prime})=10$, the same result can be obtained by
considering the corresponding $G^{\prime}_{i}$, $1\leq i\leq 4$.

Case 4: The exists at least one subgraph of $L(T_{4})$ isomorphic to $G$ where
all four pairs of peripheral vertices use a color each.
Let us consider $\mathbf{f}(a)=\mathbf{f}(l)=c_{1}$,
$\mathbf{f}(b)=\mathbf{f}(k)=c_{2}$, $\mathbf{f}(g)=\mathbf{f}(f)=c_{3}$ and
$\mathbf{f}(c)=\mathbf{f}(j)=c_{4}$. From observation 3, $c_{1}\pm 1$,
$c_{2}\pm 1$, $c_{3}\pm 1$ and $c_{4}\pm 1$ must be used in $\\{b,k\\}$,
$\\{a,l\\}$, $\\{c,j\\}$ and $\\{g,f\\}$ respectively. It can be observed that
$\lambda_{1,2}(G^{\prime})=9$ only if $|c_{1}-c_{2}|=1$, $|c_{3}-c_{4}|=1$,
one of $\\{c_{1},c_{2}\\}$ is an extreme color and one of $\\{c_{3},c_{4}\\}$
is the other extreme color. Without loss of generality, consider $c_{1}=0$,
$c_{4}=9$, $c_{2}=c_{1}+1=1$ and $c_{3}=c_{4}-1=8$. So $c_{2}+1=2$ and
$c_{3}-1=7$ are two distinct unused colors. Without loss of generality,
consider $c_{8}=c_{2}+2$, $c_{5}=c_{8}+1$, $c_{6}=c_{5}+1$ and
$c_{7}=c_{6}+1$. Since $|c_{3}-c_{4}|=1$ and $d(g,p_{4})=d(g,q_{4})=2$, we get
$\mathbf{f}(p_{4})\neq c_{4}$ and $\mathbf{f}(q_{4})\neq c_{4}$. Similarly,
$\mathbf{f}(r_{4})\neq c_{1}$ and $\mathbf{f}(s_{4})\neq c_{1}$. From
observation 2, $c_{5}$ can only be reused at $\\{s_{4},r_{4}\\}$ in
$G^{\prime}_{4}$ but $\mathbf{f}(s_{4})\neq c_{5}$ and $\mathbf{f}(r_{4})\neq
c_{5}$ as $d(h,s_{4})=d(h,r_{4})=2$ and $\mathbf{f}(h)=c_{8}=c_{5}-1$.
Therefore, only $c_{7}$ can be reused in $\\{p_{4},q_{4}\\}$. From observation
4, one of $c_{7}\pm 1$ must remain unused in $G^{\prime}_{4}$ as
$(c_{4}-c_{7})=3$. Hence $\lambda_{1,2}(G_{1})\geq 11$. For other assignment
of central vertices and for the case when $\lambda_{1,2}(G^{\prime})=10$, we
can obtain the same result by considering the corresponding $G^{\prime}_{i}$,
$1\leq i\leq 4$.

###  2.3 Triangular Grid

For any vertex $u$, the set of vertices which are adjacent to $u$ is called
$N(u)$. Let us define $N(S)=\\{\cup_{u\in S}N(u):u\in S\\}$. Let $v$ be any
vertex in $T_{6}$. Consider the subgraph $G_{v}(V,E)$ of $T_{6}$ centering $v$
as shown in Figure 5, where $V=N(v)\cup N(N(v))$ and $E$ is set of all the
edges which are incident to $u$ where $u\in N(v)$. Observe that in $G_{v}$,
for any two edges $e_{1}$ and $e_{2}$, $d(e_{1},e_{2})\leq 3$. Now we define
the following three sets of edges $S_{1}$, $S_{2}$ and $S_{3}$:

Figure 5:  A subgraph $G_{v}$ of $T_{6}$

$S_{1}$: Edges of $G_{v}$ incident to $v$.

$S_{2}$: Edges of $G_{v}$ whose both end points incident to $e_{1}$ and
$e_{2}$ where $e_{1},\ e_{2}\in S_{1}$.

$S_{3}$: $E\setminus(S_{1}\cup S_{2})$.

Consider the $6$-cycle, $H_{v}$ formed with the edges of $S_{2}$ in $G_{v}$.
We say $e$ and $e_{1}$ as a pair of opposite edges in $H_{v}$ iff
$d(e,e_{1})=3$. This implies that the same color can be used at a pair of
opposite edges in $L(1,2)$-edge labeling. An edge $e$ covers the set of edges
$E^{\prime}$ if for every $e^{\prime}\in E^{\prime}$, $d(e,e^{\prime})\leq 2$.
This implies that a color used at $e$ can not be used at any edge
$e^{\prime}\in E^{\prime}$ in $L(1,2)$-edge labeling. Now we have the
following lemmas.

######  Lemma 2.11.

If $c$ is a color used to color an edge $e$ in $S_{1}$, then $c$ can not be
used in $E\setminus e$.

######  Proof 2.12.

Since $e$ is incident to $v$, for any other edge $e_{1}\in E$, $d(e,e_{1})\leq
2$. Hence $f^{\prime}(e_{1})\neq c$ for $L(1,2)$-edge labeling, where
$f^{\prime}(e_{1})$ denotes the color of $e_{1}$.

######  Lemma 2.13.

If $c$ is a color used to color an edge in $S_{1}$, then $c+1$ and $c-1$ both
can be used at most once in $G_{v}$.

######  Proof 2.14.

Let $e$ be an edge in $S_{1}$ such that $f^{\prime}(e)=c$. Since $e$ is
incident to $v$, for any other edge $e_{1}\in E$, $d(e,e_{1})\leq 2$. Let
$S_{e}=\\{e_{1}:d(e,e_{1})=1\\}$. For $L(1,2)$-edge labeling, $c+1$ can only
be used in an edge $e_{1}$ in $S_{e}$. It can be noted that for any two edges
$e_{1},e_{2}\in S_{e}$, $d(e_{1},e_{2})\leq 2$. Hence $c+1$ can be used at
most once. Proof for $c-1$ can be done in similar manner.

######  Lemma 2.15.

If $c$ is a color used to color an edge $e$ in $S_{2}$, then $c$ can be used
at most one edge in $E\setminus e$ in $G_{v}$.

######  Proof 2.16.

Note that $c$ can not be used at any edge in $S_{1}$. Here $c$ can be used at
the opposite edge $e_{1}$ of $e$ in $S_{2}$ or at an edge $e_{2}$ in $S_{3}$,
which is adjacent to $e_{1}$. When $c$ is used at $e$ and $e_{1}$, then $c$
can not be used again in $G_{v}$ as $e$ and $e_{1}$ together cover all the
edges of $G_{v}$. When $c$ is used at $e$ and $e_{2}$, $c$ can not be used
again in $G_{v}$ as $e$ and $e_{2}$ together also cover all the edges of
$G_{v}$.

######  Lemma 2.17.

If $c$ is a color used to color an edge $e$ in $S_{2}$, then $c+1$ and $c-1$
both can be used at most twice in $G_{v}$.

######  Proof 2.18.

Suppose $e_{1}$ be an edge colored with $c+1$. If $e_{1}$ is not adjacent to
$e$ then $d(e_{1},e)=3$. From statement of lemma 2.15, it follows that there
does not exist two edges along with $e$ in $G_{v}$ which are mutually distance
$3$ apart, otherwise $c$ would have been used for three times. Hence $c+1$ can
be used at most once.

When $e_{1}$ is adjacent to $e$, $e_{2}$ can be colored with $c+1$ if $e_{2}$
is at distance $3$ apart from both $e_{1}$ and $e$. Again from the statement
of lemma 2.15, it follows that there does not exist two edges along with $e$
in $G_{v}$ which are mutually distance $3$ apart, otherwise $c$ would have
been used for three times. So, $c+1$ can be used at most twice, one in one of
the edges adjacent to $e$ and other in one of the edges which are at distance
$3$ apart from $e$. Proof for $c-1$ can be done in similar manner.

######  Lemma 2.19.

If $c$ is a color used to color an edge $e$ in $S_{3}$, then $c$ can be used
at most twice in $E\setminus e$.

######  Proof 2.20.

It follows from Figure 5 that exactly one end point of $e$ is incident to a
vertex in $H_{v}$. Note that for any walk through $H_{v}$, every third vertex
is distance $2$ apart. So edges incident to those vertices are distance $3$
apart. Since the order of $H_{v}$ is $6$, there can be at most $6/2=3$
vertices which are mutually distance $2$ apart. Hence $c$ can be used thrice.

######  Lemma 2.21.

If $c$ is a color used to color an edge $e$ in $S_{3}$, then $c+1$ and $c-1$
both can be used at most thrice in $G_{v}$.

######  Proof 2.22.

We know that $c+1$ can be used at an edge adjacent to $e$. From lemma 2.19 it
is clear that $c$ can be used at most thrice. So, $c+1$ can also be used at
most thrice, where each such edge is adjacent to one of the three edges
colored with $c$. It can be proved similarly for $c-1$.

######  Lemma 2.23.

  1. i.

To color the edges of $S_{1}$, at least $6$ colors are required.

  2. ii.

To color the edges of $S_{2}$, at least $3$ colors are required.

  3. iii.

To color the edges of $S_{3}$, at least $6$ colors are required.

######  Proof 2.24.

i. From lemma 2.11, every edge of $S_{1}$ has an unique color. As there are
$6$ edges in $S_{1}$, $6$ distinct colors are required here.

ii. In $S_{2}$, there are $3$ pairs of opposite edges. Each pair of opposite
edges requires at least one unique color. So at least $3$ colors are required.

iii. A color can be used thrice in $S_{3}$ by lemma 2.19. In $S_{3}$, there
are $18$ edges. So, at least $6$ colors are required.

######  Theorem 2.25.

For any optimal labeling of $G_{v}$, $6$ consecutive colors including either
the minimum color or the maximum color must be used in $S_{1}$.

######  Proof 2.26.

It is clear from lemma 2.23.i that $S_{1}$ needs at least $6$ colors to color
its edges. From lemma 2.13, note that if $c$ is a color used in an edge of
$S_{1}$ then both $c+1$ and $c-1$ can be used at most once in $G_{v}$. Whereas
a color can be used twice in $S_{2}$ and thrice in $S_{3}$. Thus our aim
should be to minimize the number of colors which can be used only once in
$G_{v}$. This implies that consecutive colors should be used in $S_{1}$ for
optimal coloring. If the minimum color ($min$) or the maximum color ($max$) is
used in $S_{1}$ then further benefit can be achieve as $min-1$ or $max+1$ does
not exist. Therefore, optimal span can be achieved only when the colors of
$S_{1}$ are consecutive including either $min$ or $max$.

######  Lemma 2.27.

If three consecutive colors $c$, $c+1$, $c+2$ are used thrice each in $S_{3}$
then neither $c-1$ nor $c+3$ can be used in $S_{3}$.

######  Proof 2.28.

Observe that there are exactly $2$ sets of three alternating vertices in
$H_{v}$ where a color can be used thrice at edges incident to any set of
alternating vertices. If $c-1$ would have been used in $S_{3}$ then either it
was used at an edge adjacent to the edges colored with $c$ or at an edge
distance $3$ apart from the edge colored with $c$. Now observe that $c$ and
$c-1$ are used at two edges of $S_{3}$ which form a triangle with one edge of
$S_{2}$. Suppose $c$, $c-1$ be the colors used at those two edges $e,e_{1}\in
S_{3}$ respectively, where $e$ is incident to $u$ and $e_{1}$ is incident to
$w$ where $uw\in S_{2}$. Note that $c$ is used thrice in $S_{3}$. Then $c$
must be reused at an edge incident to $x$, and $xw\in S_{2}$. So $c$ and $c-1$
are used at two edges at distance $2$ apart, which violets the condition of
$L(1,2)$-edge labeling. Hence $c-1$ can not be used in $G_{v}$. Similarly it
can be shown that $c+3$ can also not be used in $G_{v}$. This implies that no
$4$ consecutive colors can be used thrice each in $G_{v}$.

######  Theorem 2.29.

333Theorem is modified from that of the conference version Bandopadhyay et al.
(2020).

$\lambda^{\prime}_{1,2}(G_{v})\geq 16$.

######  Proof 2.30.

By Theorem 2.25, $6$ consecutive colors must be used to color the edges of
$S_{1}$. Recall that, we assume the minimum color is used at $S_{1}$. Let
$c_{1}$ be the maximum color used in $S_{1}$ and $c$ be the minimum color used
in $S_{2}$. Now we consider the coloring of the edges in $S_{2}\cup S_{3}$. If
the edges of $S_{2}$ have all consecutive colors $c,c+1,\cdots,c+5$ then $6$
colors are needed for $S_{2}$. From Lemma 2.15, any color $c^{\prime}$, used
in $S_{2}$ can be reused at most once more in $G_{v}$ unless
$c^{\prime}=c_{1}+1$ (Lemma 2.13). Thus we can color at most $6$ edges in
$S_{3}$ using those colors. From Lemma 2.17, the color $c+6$ can be used at
most twice in $G_{v}$. Note that color $c_{1}+1$ can be used at most once in
$G_{v}$. So far, at most $9$ edges in $S_{3}$ are colored. So at least $9$
edges are left to be colored in $S_{3}$. So at least $3$ more colors are
needed for $S_{3}$, as any color can be used at most thrice in $S_{3}$.
However, from Lemma 2.27, in that case, all of $c+7$, $c+8$ and $c+9$ can not
be used thrice each in $S_{3}$. Thus at least $c+10$ is needed for $G_{v}$.
Since $c-6$ is used in $S_{1}$, we get
$\lambda^{\prime}_{1,2}(G_{v})\geq(c+10)-(c-6)=16$. Now, consider the case
when $4$ colors are used in $S_{2}$. Observe that then in any possible
coloring, at least $3$ colors can be used at most twice in $S_{3}$. Therefore,
at most $9$ edges of $S_{3}$ can be colored. Hence here too, we can argue that
$c+10$ must be used in $G_{v}$. In a similar manner, we can argue that when
five colors are used in $S_{2}$, the color $c+10$ must be used in $G_{v}$.
Hence in all the cases discussed above, we get
$\lambda^{\prime}_{1,2}(G_{v})\geq 16$.

Now consider the case when only three colors say $c$, $c^{\prime}$,
$c^{\prime\prime}$ are used in $S_{2}$. Without loss of generality assume
$c^{\prime}-c\geq 2$ and $c^{\prime\prime}-c^{\prime}\geq 2$.

First consider the cases assuming $c_{1}+1=c-1$. Observe that if $c+1\neq
c^{\prime}-1$ and $c^{\prime}+1\neq c^{\prime\prime}-1$, then $c\pm
1,c^{\prime}\pm 1,c^{\prime\prime}\pm 1$ can color at most $(1+5\times 2)=11$
edges of $S_{3}$. So at least $7$ edges are left to be colored in $S_{3}$
requiring at least $3$ more colors. So at least $9$ colors are required for
$S_{3}$ and hence $\lambda^{\prime}_{1,2}(G_{v})\geq 17$. If
$c^{\prime\prime}$ is maximum color, then $c^{\prime\prime}+1$ can not be used
and in this case too, at least $17$ colors are required for $G_{v}$ and hence
$\lambda^{\prime}_{1,2}(G_{v})\geq 16$. Now we consider the case when
$c+1=c^{\prime}-1$ but $c^{\prime}+1\neq c^{\prime\prime}-1$. Here
$c+1,c^{\prime}+1,c^{\prime\prime}\pm 1$ can color at most $8$ edges of
$S_{3}$. Thus using $c-1$ also we are able to color at most $9$ edges in
$S_{3}$. Therefore at least $9$ edges are left to be colored in $S_{3}$
requiring at least $3$ more colors. So at least $8$ colors are required for
$S_{3}$ and hence $\lambda^{\prime}_{1,2}(G_{v})\geq 16$. Similarly we can
argue that $\lambda^{\prime}_{1,2}(G_{v})\geq 16$ when $c+1\neq c^{\prime}-1$
$c^{\prime}+1=c^{\prime\prime}-1$. If $c+1=c^{\prime}-1$ and
$c^{\prime}+1=c^{\prime\prime}-1$, then $c$, $c+2$ and $c+4$ are used in
$S_{2}$. Here $c\pm 1,c+3,c+5$ can color at most $7$ edges of $S_{3}$. So at
least $11$ edges are left to be colored in $S_{3}$ requiring at least $4$ more
colors. So at least $8$ colors are required for $S_{3}$ and hence
$\lambda^{\prime}_{1,2}(G_{v})\geq 16$. Similarly, one can verify that when
$c_{1}+1\neq c-1$ the bound remains the same for all the cases. Thus
considering all cases, $\lambda^{\prime}_{1,2}(G_{v})\geq 16$.

We assume that the minimum color is used in $S_{1}$. The maximum color can be
used at most thrice in $S_{3}$ and at most twice in $S_{2}$. In all cases,
there exists a vertex say $v^{\prime}$ in $H_{v}$ such that color of any edge
incident to $v^{\prime}$ is neither minimum nor maximum. Now we consider the
subgraph $G_{v^{\prime}}$ of $T_{6}$ centering $v^{\prime}$ and isomorphic to
$G_{v}$. Let $min_{1}$ and $max_{1}$ be the minimum and maximum colors used in
$S^{\prime}_{1}$ in $G_{v^{\prime}}$.

######  Lemma 2.31.

444Lemma is modified from that of the conference version Bandopadhyay et al.
(2020).

If $max_{1}-min_{1}\geq 7$, i.e., there exists at least two intermediate
colors between $min_{1}$ and $max_{1}$ which are not used in $S^{\prime}_{1}$,
then $\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq 18$.

######  Proof 2.32.

At least two unused colors $c_{1},c_{2}$ are there in $S^{\prime}_{1}$ such
that $\forall c\in\\{c_{1},~{}c_{2}\\}$, either $c+1$ or $c-1$ is used in
$S^{\prime}_{1}$. From lemma 2.13, $c_{1}$, $c_{2}$, $min_{1}-1$ and
$max_{1}+1$ can be used at most once each in $G_{v^{\prime}}$. Let
$x^{\prime}$ be the number of colors required for $G_{v^{\prime}}$. Let us
first consider that $6$ colors are used in $S^{\prime}_{2}$. These colors can
be reused at most once each in $S^{\prime}_{3}$. Consider that all of
$c_{1},~{}c_{2},~{}min_{1}-1$ and $max_{1}+1$ are also used once each in
$S^{\prime}_{3}$. So at most $(6+4)=10$ edges of $S^{\prime}_{3}$ have been
colored so far. So at least $(18-10)=8$ edges are left to be colored in
$S^{\prime}_{3}$ requiring at least $3$ more colors. So,
$x^{\prime}\geq(6(for\ S^{\prime}_{1})+6(for\ S^{\prime}_{2})+7(for\
S^{\prime}_{3}))=19$ and hence $\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq
18$. Now assume $5$ colors are used in $S^{\prime}_{2}$. The only possibility
is that $4$ colors must be used once each in $S^{\prime}_{2}$ and $1$ color
should be used two times in $S^{\prime}_{2}$. These $4$ colors can be reused
at most once each in $S^{\prime}_{3}$. So at most $(4+4)=8$ edges of
$S^{\prime}_{3}$ have been colored so far. So at least $4$ more colors are
required to color the remaining edges of $S^{\prime}_{3}$. So,
$x^{\prime}\geq(6+5+8)=19$ and hence
$\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq 18$. If $4$ colors are used in
$S^{\prime}_{2}$, similarly we can show that
$\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq 18$.

Now consider that $3$ colors are used two times each in $S^{\prime}_{2}$.
These $3$ colors can not be used anymore in $S^{\prime}_{3}$. So at least
$(18-4)=14$ edges are left to be colored in $S^{\prime}_{3}$, requiring at
least $5$ more colors. At least $4$ out of these $5$ colors must be used three
times each in $S^{\prime}_{3}$. From Lemma 2.27, if $3$ consecutive colors are
used $3$ times each in $S^{\prime}_{3}$, then at least one color can not be
used in $S^{\prime}_{3}$ resulting $\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq
18$. Otherwise, at most two sets of two consecutive colors can be reused three
times each in $S^{\prime}_{3}$. In that case, at least three colors
$x,~{}y,~{}z$ are there such that for all $w\in\\{x,~{}y,~{}z\\}$ either $w+1$
or $w-1$ is in one of $S^{\prime}_{1}$ or $S^{\prime}_{2}$. So each of them
can not be used three times each. So these $5$ colors can color at most
$(3\times 2+2\times 3)=12$ edges in $S^{\prime}_{3}$, requiring at least $1$
more color for $S^{\prime}_{3}$. So at least $(4+6)=10$ colors are required
for $S^{\prime}_{3}$ and hence $\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq
18$. For all other cases we also get
$\lambda^{\prime}_{1,2}(G_{v^{\prime}})\geq 18$ using similar argument.

######  Theorem 2.33.

555Theorem is modified from that of the conference version Bandopadhyay et al.
(2020).

$\lambda^{\prime}_{1,2}(T_{6})\geq 18$.

######  Proof 2.34.

Assume that $x$ be a vertex which is not adjacent to edges colored with
maximum and minimum colors used in $G_{x}$. Let us consider $G_{x}$ is not
colored and $u$, $w$ be two vertices of $H_{x}$ in $G_{x}$. Let us define
$S_{x1}$ as the set of edges adjacent to $x$. We consider the following two
cases.

When $w\in N(u)$: $u$ and $w$ are connected by an edge $e$. Let
$\\{c_{1},\cdots,c_{6}\\}$ and $\\{c^{\prime}_{1},\cdots,c^{\prime}_{6}\\}$ be
two sequences consisting of consecutive colors are used at the edges incident
to $u$ and $w$ respectively. It is possible to assign consecutive colors at
those edges when $e$ is colored with either $c_{6}=c^{\prime}_{1}$ or
$c_{1}=c^{\prime}_{6}$. Now observe two edges $e^{\prime}$ and
$e^{\prime}_{1}$ of $S_{x1}$ are already colored and those are not
consecutive. Note that
$|f^{\prime}(e^{\prime})-f^{\prime}(e^{\prime}_{1})|\geq 2$. If
$|f^{\prime}(e^{\prime})-f^{\prime}(e^{\prime}_{1})|=2$ then
$f^{\prime}(e^{\prime})$ and $f^{\prime}(e^{\prime}_{1})$ is neither minimum
nor maximum color used in $u$ and $w$. Then any color of any other edge in
$S_{x1}$ is neither consecutive to $f^{\prime}(e^{\prime})$ nor
$f^{\prime}(e^{\prime}_{1})$. So $max-min\geq 7$ where $min$ and $max$ be the
minimum and maximum colors used in $S_{x1}$. If
$|f^{\prime}(e^{\prime})-f^{\prime}(e^{\prime}_{1})|>2$, then also $max-
min\geq 7$. Hence from lemma 2.31, $\lambda^{\prime}_{1,2}(G_{x})\geq 18$.

When $w\notin N(u)$: Note that $x\in\\{N(u)\cap N(w)\\}$. Let two sequences
$\\{c_{1},\cdots,c_{6}\\}$ and $\\{c^{\prime}_{1},\cdots,c^{\prime}_{6}\\}$
consisting of consecutive colors are used at the edges incident to $u$ and $w$
respectively. Let $uv$ and $wv$ are $e^{\prime}$ and $e^{\prime}_{1}$
respectively. If $f^{\prime}(e^{\prime})$ and $f^{\prime}(e^{\prime}_{1})$ are
consecutive then either $f^{\prime}(e^{\prime})=c_{6},\
f^{\prime}(e^{\prime}_{1})=c^{\prime}_{1}$ or $\
f^{\prime}(e^{\prime})=c_{1},\ f^{\prime}(e^{\prime}_{1})=c^{\prime}_{6}$. Now
observe that for any other edge $e$ in $S_{x1}$,
$|f^{\prime}(e)-f^{\prime}(e^{\prime})|>2$ implying $max-min\geq 7$ where
$min$ and $max$ be the minimum and maximum colors used inc $S_{x1}$. If
$f^{\prime}(e^{\prime})$ and $f^{\prime}(e^{\prime}_{1})$ are not consecutive
then $|f^{\prime}(e^{\prime})-f^{\prime}(e^{\prime}_{1})|\geq 2$. If
$|f^{\prime}(e^{\prime})-f^{\prime}(e^{\prime}_{1})|=2$ then the intermediate
color must be used at an edge $e\in S_{x1}$. There are still $4$ edges remain
uncolored. It can be checked that for any coloring of the rest of the graph,
there exists a vertex $y\in H_{x}$ or $y\in N(z),z\in H_{x}$, for which $max-
min\geq 7$ where $min$ and $max$ be the minimum and maximum colors used to
color the edges incident to $y$ and they are neither maximum nor minimum color
used in $G_{x}$. Hence from lemma 2.31, $\lambda^{\prime}_{1,2}(G_{x})\geq
18$.

###  2.4 Octagonal Grids

Graph $G$ shown in figure 6 is a subgraph of the infinite octagonal grid
$T_{8}$, consisting of all the edges incident to the vertices
$a,b,c,\cdots,p$. Let $H$ be a subgraph of $G$ consisting of all the edges
incident to the vertices $g,f,k,j$. Clearly $|E(H)|=26$, $|E(G)|=86$ and
$|E(G\setminus H)|=60$. Observe that the distance between any two edges in $H$
is at most two. Hence in $H$ no color can be used twice. Since $|E(H)|=26$, we
get $\lambda^{\prime}_{1,2}(T_{8})\geq\lambda^{\prime}_{1,2}(H)\geq 25$. If
one color in $\\{0,1,\cdots,25\\}$ is unused at $H$ then
$\lambda^{\prime}_{1,2}(H)\geq 26$. Here our goal is to prove
$\lambda^{\prime}_{1,2}(G)\geq 26$. Therefore, we can proceed assuming that no
color in $\\{0,1,\cdots,25\\}$ is unused in $H$ and we show that, at least one
extra color is needed for proper coloring of $G$. Here, we define a new notion
as fork. We say that the three edges $e_{1}=(f,c),e_{2}=(f,d),e_{3}=(f,e)$ are
forming a fork at vertex $f$ and denoted as $\mathcal{F}_{f}$. The edges
forming the forks $\mathcal{F}_{f}$, $\mathcal{F}_{g}$, $\mathcal{F}_{j}$ and
$\mathcal{F}_{k}$ at vertices $f$, $g$, $j$ and $k$ respectively are all
marked by bold edges in the figure. Now, we state the following observations
regarding the reusability of the colors used in $H$:

###### Observation 5

There exists $14$ edges in $H$, each color used there can be reused at most
twice in $G\setminus H$.

######  Proof 2.35.

Consider the graph
$H^{\prime}=E(H)\setminus(\mathcal{F}_{f}\cup\mathcal{F}_{g}\cup\mathcal{F}_{j}\cup\mathcal{F}_{k})$.
Note that $|E(H^{\prime})|=26-4\times 3=14$. Our claim is that each color used
in $H^{\prime}$ can be reused at most twice in $G\setminus H$. One can verify
that, repetition pattern of the colors of the edges $(b,f)$, $(i,g)$, $(h,j)$,
$(o,k)$, $(j,n)$, $(k,e)$ and $(f,l)$ are symmetric to that of the color used
in $(g,c)$. In this sense, edges $(g,j)$, $(j,k)$ and $(k,f)$ are symmetric to
$(g,f)$; and edge $(g,k)$ is symmetric to $(j,f)$. So, our goal is to show the
following: if color $c^{\prime}$ is used in any of these three edges then
$c^{\prime}$ can be reused at most twice in $G\setminus H$. Let us first take
the edge, $e^{\prime}=(g,c)$, and assume, $f^{\prime}(e^{\prime})=c^{\prime}$.
The color $c^{\prime}$ can be used only in some of the edges incident on the
vertices $l,m,n,o,p$. Note that $\\{l,m,n\\}$ and $\\{o,p\\}$ are two cliques.
Hence there can not be more than two edges, where the color $c^{\prime}$ can
be reused without violating the constraints of $L(1,2)$-edge labeling. Now,
take the edge, $e^{\prime}=(g,f)$. Assume that,
$f^{\prime}(e^{\prime})=c^{\prime}$. The color $c^{\prime}$ can be reused in
some edges incident on the vertices $m,n,o,p$, where $\\{m,n\\}$ and
$\\{o,p\\}$ are two cliques. Hence here also, color $c^{\prime}$ can be reused
at most twice in $G\setminus H$. Now we have one more edge to analyse, i.e,
$e^{\prime}=(j,f)$. Let $f^{\prime}(e^{\prime})=c^{\prime}$. There are only
two vertices $a$ and $m$, in the graph $G$, whose incident edges can get color
$c^{\prime}$. Hence any color used in $H^{\prime}$ can be reused at most twice
in $G\setminus H$.

Figure 6: Sub graph $G$ of $T_{8}$

###### Observation 6

There exists $12$ edges in $H$, each color used there can be reused at most
thrice in $G\setminus H$.

######  Proof 2.36.

Here we discuss about the edges in $E(H)\setminus E(H^{\prime})$, i.e.,
$(\mathcal{F}_{f}\cup\mathcal{F}_{g}\cup\mathcal{F}_{j}\cup\mathcal{F}_{k})$.
One can observe that, $\mathcal{F}_{f}$ is symmetric to all other
$\mathcal{F}_{x},\forall x\in\\{g,j,k\\}$. So, if we can prove the statement
for all edges in $\mathcal{F}_{f}=\\{e_{1},e_{2},e_{3}\\}$ then we are done.
Note that, all the colors used in edges $\\{e_{1},e_{2},e_{3}\\}$ can be
reused at some edges incident on the vertices $m,n,o,p,i,h,a$. Note that
$\\{m,n\\}$, $\\{o,p,i\\}$ and $\\{h,a\\}$ are three cliques. Hence, there
does not exist more than three vertices at a time, such that $c^{\prime}$ can
be used at edges incident on them.

As $|E(G\setminus H)|=60$ and $\lambda^{\prime}_{1,2}(H)=25$, from
Observations 5 and 6 it is evident that, to make
$\lambda^{\prime}_{1,2}(G)=25$ as well, we need to reuse at least eight colors
($14\times 2+4\times 2+8\times 3=60)$ thrice each in $G\setminus H$. Now, in
next two lemmas we discuss about reusability of a color for three times and
its constraints.

######  Lemma 2.37.

If $c^{\prime}$ be a color used at a fork edge in $H$ and reused thrice in
$G\setminus H$ then $c^{\prime}\pm 1$ must be used at the other two edges of
that fork, otherwise $\lambda^{\prime}_{1,2}(H)\geq 26$.

######  Proof 2.38.

From Observations 5 and 6 it is clear that, only the colors used at the four
forks $\mathcal{F}_{f},\mathcal{F}_{g},\mathcal{F}_{j},\ \text{and}\
\mathcal{F}_{k}$ in $H$ can be reused thrice in $G\setminus H$. If we can
prove for any one of the four forks then symmetrically it can be shown for
others too. So, let us consider the fork
$\mathcal{F}_{f}=\\{e_{1},e_{2},e_{3}\\}$. Without loss of generality assume
$f^{\prime}(e_{1})=c^{\prime}$. Note that $c^{\prime}$ can be reused at some
edges incident on the vertices $m,n,o,p,i,h,a$. Since $\\{m,n\\}$,
$\\{o,p,i\\}$ and $\\{h,a\\}$ are three cliques, $c^{\prime}$ must be reused
at the three edges incident on a vertex from $\\{m,n\\}$, $\\{o,p,i\\}$ and
$\\{h,a\\}$ each, respectively. All edges in $H$ which are not incident on $f$
are exactly distance $2$ apart from $e_{1}$ and hence $c^{\prime}\pm 1$ can
not be used there for any $L(1,2)$-edge labelling. We now consider the
possibility of using $c^{\prime}\pm 1$ at the five edges
$(f,b),(f,g),(f,j),(f,k),(f,l)$ which are incident on $f$ but not in
$\\{e_{2},e_{3}\\}$. To reuse $c^{\prime}$ thrice in $G\setminus H$,
$c^{\prime}$ must be used at an edge incident on a vertex in $\\{h,a\\}$ but
not incident on a vertex in $\\{b,g\\}$. Both $(f,b)$ and $(f,g)$ are exactly
distance $2$ apart from any such edge. Hence $c^{\prime}\pm 1$ can not be used
at $(f,b)$ and $(f,g)$. Also it is clear that, $c^{\prime}$ must be reused at
an edge incident on a vertex in $\\{m,n\\}$ but not incident on a vertex in
$\\{l,k\\}$, which is exactly symmetric to the previous case. So,
$c^{\prime}\pm 1$ can not be used at $(f,l)$ and $(f,k)$ as well. Now consider
the case when $c^{\prime}$ must be used at an edge incident on a vertex in
$\\{o,p,i\\}$ but not incident on $j$. Here also $(f,j)$ is distance $2$ apart
from any such edge and hence $c^{\prime}\pm 1$ can not be used there.
Therefore, $c^{\prime}\pm 1$ have to be used at edges $e_{2}$ and $e_{3}$. If
we consider $f^{\prime}(e_{2})=c^{\prime}$ (or,
$f^{\prime}(e_{3})=c^{\prime}$) then also, we can argue in a similar way and
show that, other than $e_{1}$ and $e_{3}$ (or, $e_{1}$ and $e_{2}$), there is
no edges in $H$ which can get colors $c^{\prime}\pm 1$. However, we must have
to use $c^{\prime}\pm 1$ in $H$ as otherwise $\lambda^{\prime}_{1,2}(H)\geq
26$.

Now, if all three colors $c^{\prime}-1,c^{\prime},c^{\prime}+1$ reused thrice
each in $G\setminus H$ then from Lemma 2.37 we can conclude that
$c^{\prime}\pm 2$ can not be used in $H$. So, clearly all three of the colors
can not be used thrice each. Next lemma says about the reusability of these
three colors.

######  Lemma 2.39.

Only two colors used at a fork in $H$ can be reused thrice in $G\setminus H$
if no color is unused in $H$, that too when one of them is either the minimum
or the maximum color in that span.

######  Proof 2.40.

By Lemma 2.37, it is clear that if $c^{\prime}$ is used at an edge in a fork
in $H$ and reused thrice in $G\setminus H$ then, both of the colors
$c^{\prime}\pm 1$ have to be used at the rest two edges of the fork.
Similarly, if $c^{\prime}+1$ (or, $c^{\prime}-1$) is used of at an edge of the
fork and reused three times in $G\setminus H$ then $c^{\prime}+2$ (or,
$c^{\prime}$) and $c^{\prime}$ (or, $c^{\prime}-2$) have to be used at the
other two edges of that fork, which is not possible as $c^{\prime}-1$ (or,
$c^{\prime}+1$) and $c^{\prime}$ have already been used at other two edges of
that fork. So, the color $c^{\prime}+2$ (or, $c^{\prime}-2$) will remain
unused in $H$, which makes $\lambda^{\prime}_{1,2}(H)\geq 26$. So, if any of
$c^{\prime}\pm 1$ is reused thrice in $G\setminus H$ along with $c^{\prime}$
then one of $c^{\prime}\pm 2$ will be unused in $H$ and increase the span.
However, observe that, if we can make sure that $c^{\prime}+1=max$ or
$c^{\prime}-1=min$ then $c^{\prime}+2$ or $c^{\prime}-2$ does not belong to
the span, where $max$ and $min$ be the maximum and the minimum colors in the
span, respectively. This implies that when $c^{\prime}+1=max$ (or,
$c^{\prime}-1=min$), both $c^{\prime}$ and $c^{\prime}+1$ (or, $c^{\prime}-1$)
can be reused thrice each in $G\setminus H$.

######  Theorem 2.41.

$\lambda^{\prime}_{1,2}(T_{8})\geq 26$.

######  Proof 2.42.

From Lemma 2.39 it can be said that, if no color is unused in $H$ then only
one color used at an edge in a fork in $H$, can be reused three times in
$G\setminus H$ unless that color is $min+1$ or $max-1$. There are four forks
in $H$. So, two colors $min$ and $min+1$ from one fork having colors
$\\{min,min+1,min+2\\}$, two colors $max-1$ and $max$ from another fork having
colors $\\{max-2,max-1,max\\}$, one color each from the remaining two forks,
can be reused thrice each in $G\setminus H$. Hence, total six colors used in
$H$ can be reused thrice each in $G\setminus H$, rest $20$ colors can be
reused at most twice. Total number of edges of $G\setminus H$ that can be
colored using the colors used in $H$ is $(20\times 2+6\times 3)=58$. But $60$
edges are there in $G\setminus H$. Hence, at least one more color is required.

##  3 Conclusions

Here we improve lower and upper bounds for $L(2,1)$-edge labeling of
$T_{3},T_{4},T_{6}$ and $T_{8}$ using structural properties. An interesting
problem will be to improve or introduce new bounds on those graphs for other
values of $h$ and $k$ or to examine different variants of $L(h,k)$-labeling.

## References

  * Bandopadhyay et al. (2020) S. Bandopadhyay, S. C. Ghosh, and S. Koley.  Improved bounds on the span of L(1,2)-edge labeling of some infinite regular grids.  In _Graphs and Combinatorial Optimization: from Theory to Applications (The 18th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2020), September 14-16, 2020). AIRO Springer Series, vol 5. Springer, Cham_ , 2020.
  * Calamoneri (2011) T. Calamoneri.  The _L_(_h_ , _k_)-labelling problem: An updated survey and annotated bibliography.  _Comput. J._ , 54(8):1344–1371, 2011.
  * Calamoneri (2015) T. Calamoneri.  Optimal _L_(j, k)-edge-labeling of regular grids.  _Int. J. Found. Comput. Sci._ , 26(4):523–535, 2015.
  * Chen and Lin (2012) Q. Chen and W. Lin.  L(j, k)-labelings and l(j, k)-edge-labelings of graphs.  _Ars Comb._ , 106:161–172, 2012.
  * Griggs and Jin (2007) J. R. Griggs and X. T. Jin.  Real number labelings for paths and cycles.  _Internet Mathematics_ , 4(1):65–86, 2007.
  * Griggs and Yeh (1992) J. R. Griggs and R. K. Yeh.  Labelling graphs with a condition at distance 2.  _SIAM J. Discrete Math._ , 5(4):586–595, 1992\.
  * Hale (1980) W. K. Hale.  Frequency assignment: Theory and applications.  _Proceedings of the IEEE_ , 68(12):1497–1514, Dec 1980.  ISSN 1558-2256.
  * He and Lin (2014) D. He and W. Lin.  L(1, 2)-edge-labelings for lattices.  _Applied Mathematics-A Journal of Chinese Universities_ , 29:230–240, 06 2014.
  * Lin and Wu (2013) W. Lin and J. Wu.  Distance two edge labelings of lattices.  _J. Comb. Optim._ , 25(4):661–679, 2013.
  * Roberts (2003) F. Roberts.  Working group agenda.  In: DIMACS/DIMATIA/Renyi Working Group on Graph Colorings and their Generalizations, 2003.