Improved Bounds on the Span of $L(1,2)$-edge Labeling of Some Infinite Regular Grids

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 }_{h,k}^{\prime }(G)$ is the minimum $n$ such that $G$ admits an $L(h,k)$-edge labeling. Here our main focus is on finding ${\lambda }_{1,2}^{\prime }(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\le {\lambda }_{1,2}^{\prime }(T_3)\le 8$, $10\le {\lambda }_{1,2}^{\prime }(T_4)\le 11$, $16\le {\lambda }_{1,2}^{\prime }(T_6)\le 20$ and $25\le {\lambda }_{1,2}^{\prime }(T_8)\le 28$. Here we settle two long standing open questions i.e. ${\lambda }_{1,2}^{\prime }(T_3)$ and ${\lambda }_{1,2}^{\prime }(T_4)$. We show ${\lambda }_{1,2}^{\prime }(T_3)=7$, ${\lambda }_{1,2}^{\prime }(T_4)=11$. We also improve the bound for $T_6$ and $T_8$ and prove ${\lambda }_{1,2}^{\prime }(T_6)\ge 18$, ${\lambda }_{1,2}^{\prime }(T_8)\ge 26$.