Paper detail

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

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